Algorithms-Sorting/Searching

• Algorithm


  A set of steps that can be followed to accomplish some task
• We all use algorithms all the time without thinking about it
• Algorithms


  • Instructions need to be precise, accurate and complete
  • There may be multiple ways of doing the same task, but a good algorithm will do so in as efficient a way as possible
• Linear search


  1. Pick any record and check whether it's the one you are after

  2. If it is, stop

  3. If not, move on to next record

  4. If you run out of records then the item wasn't there
• Linear search


  • Works whether data is sorted or not
  • Best case is finding it on first guess
  • Worst case is finding it on last record
  • On average, find it after 50 guesses with 100 items
• Binary search


  1. Consider the range of possible records where your data might be

  2. Pick a record in the middle

  3. Adjust the range of records you are looking at based on whether the record is in the first or second half

  4. Repeat this process, narrowing your search each time
• Binary search


  • Only works if data is sorted
• Binary tree


  A tree-like diagram where every choice is between two options
• With a binary tree, one extra question doubles the number of possible outcomes
• Example of binary tree

  • Guessing a number between 1 and 100
• Algorithms like binary search scale up very well as one additional question doubles the number of possibilities
• Sorting algorithms


  • Insertion sort
  • Quick sort
  • Bubble sort
• Bubble sort


  1. Start at the first item in the list

  2. Compare the current item with the next item in the list

  3. If they should be the other way around then swap them

  4. Move one item to the right and repeat

  5. Repeat from step 2 until you reach the end of the list

  6. If you have made a swap since step 1 then repeat from step 1
• Basic search algorithm


  1. Start with the first item on the list

  2. Compare this item with the desired item

  3. If they don't match then if there is a next item in the list then move it and repeat from step 2

  4. If they do match then you have found the item
• Searching sorted vs unsorted lists


  • With a sorted list, you can use more sophisticated algorithms and know when to give up the search
  • The downside is you have to sort the list before searching, but this can be done separately
• Google PageRank


  An algorithm that looks at how many other websites refer to a particular website, giving each page a 'ranking'
• Google's PageRank algorithm worked so well that Google quickly outgrew most of the other search engines at the time
• Alpha testing


  Testing a product to make sure it works
• Beta testing


  Giving the product to customers/users for them to test
• Companies usually arrange both alpha and beta testing as alpha testing is like testing under perfect conditions, while beta testing is more like real life