2.1.3

• Binary search:

  • Find the middle item in the ordered list - in a list of n items do (n+1)/2 and round up if needed
  • If this is the item you're looking for, then stop the search
  • If not, compare the item you're looking for to the middle item. If it comes before the middle item, get rid of the second half of the list. If it comes after the middle item, get rid of the first half of the list
  • You'll be left with a list half the size of the original list. Repeat the steps until you find the item you're looking for
• Binary search:

  Advantage:

  • Best search choice for sorted lists
  • If the item is at a midpoint of the array, it will be found quickly
  • Efficient on larger data sets (cuts the list in half each time)

  Disadvantage:

  • The array has to be sorted
• Linear search:

  Checks each item of the list to see if its the correct one

  • Look at the first item in the unordered list
  • If this is the item you're looking for then stop the search
  • If not, then look at the next item
  • Repeat until you find the item you're looking for or you've checked every item
• Linear search:

  Advantages:

  • Doesn't need to be sorted
  • If the item to be found is at the start of the array, it will be found quickly
  • Efficient on smaller data sets

  Disadvantage:

  • Not efficient if the item is at the end of the array or not in the array
• Bubble sort:

  • Look at the first two items in the list
  • If they're in the right order, you don't have to do anything. If they're in the wrong order, swap them
  • Repeat until you reach the end of the list - this is called one pass. The last item will now be in the correct place, so don't include it in the next pass.
  • Repeat until there are no swaps in a pass
• Bubble sort:

  • When swapping items in a list, we need to use a temporary variable
  • Put 9 in temp variable
  • Copy 5 to where 9 was
  • Copy from the temp variable

  
• Bubble sort:

  Advantages:

  • Simple algorithm
  • Efficient way to check if a list is already ordered
  • Doesn't use much memory

  Disadvantages:

  • Inefficient way to sort a list
  • Because it is inefficient it doesn't cope well with a very large list of items
• Merge sort:

  • Split the list in half (the smaller lists are called sub-lists) - the second sub-list should contain the middle item
  • Repeat on each sub-list until all the lists only contain one item
  • Merge pairs of sub-lists so that each sub-list has twice as many items. Each time you merge sub-lists, sort the items into the right order
  • Repeat until you've merged all the sub-lists together
• Merge sort:

  Advantages:

  • More efficient and quicker than a bubble sort and insertion sort for large lists
  • Very consistent running time regardless of how ordered the items in the list are

  Disadvantages:

  • Slower than other algorithms for small lists
  • Even if the list is already sorted it still goes through the whole splitting and merging process
  • Uses more memory than other sorting algorithms in order to create the separate lists
• Insertion sort:

  • Look at the second item in a list
  • Compare it to all items before it and insert into the right place
  • Repeat until the last item has been inserted into the correct place
• Insertion sort:

  Advantages:

  • Intuitive way of sorting things which can be easily coded
  • Copes well with small lists
  • Sorting is done on the original list like bubble sort so requires little additional memory
  • Quick to add items to an already ordered list
  • Quick at checking that a list is already sorted

  Disadvantages:

  • Doesn't cope well with large lists