sorting & searching algorithms

• bubble sort

  • given a list of values, the computer compares adjacent pairs of elements and swaps them if they are not in the right order.
  • it will make several passes of the list until the data is in sorted order.
  • it’s a very inefficient way of sorting data, as it requires several runs through each list.
• two main methods for sorting algorithms

  • bubble sort
  • merge sort
• merge sort is an example of a ‘divide-and-conquer’ algorithm:

  • divide (the problem into a small number of pieces)
  • conquer (solve each piece, by repeatedly applying divide-and-conquer to it)
  • combine (the pieces together into a solution).
• • merge sort requires fewer steps to complete than bubble sort
  • merge sort is more difficult to implement because of it’s recursive structure (i.e. it has to call itself).
  • recursive programming can consume memory as the values need to be stored for each step down the splitting and merging.
  • this means that whilst the merge sort algorithm is more efficient - particularly for large data sets - it can be more memory intensive for a computer.
• the basic searching algorithms

  • linear search
  • binary search
• linear search 


  starting at the beginning of a list and checking each item until you find the thing you are looking for
• binary search

  • a way of looking for a piece of data in an ordered list by continually splitting the list in half
  • you then check the middle number and work out which half of the list the value to find it