2.1.3 Sorting and searching algorithms

• Bubble Sort


  Relative simple algorithm to program

  Inefficient and may take much longer to complete on large lists

  Based on multiples passes

  During a pass, work left to right, and swap pairs if they are not in order

  Keeps completing passes until one completed with no swaps
• Insertion Sort


  More efficient than bubble sort but can be relatively tricky to implement in a high-level language

  Splits a data set into a sorted and an unsorted part

  One by one, an item is moved from unsorted to sorted part

  Works backwards
• Merge Sort


  A divide and conquer algorithm

  Much more efficient than the other sorts

  Divide the list in two

  Repeats step 1 until all sublists contain one item only

  Merge two sublists so they are put in order

  Repeat step 3 until there is only one list
• Linear Search


  Relatively inefficient

  Only option if the dataset is unsorted

  Needs to be checked before you can be certain that a value is not present in a list

  Works by comparing each item in the dataset again the target
• Binary Search


  Requires a list of values to be in order (ascending or descending)

  Highly efficient

  Sects the midpoint of the dataset and if it’s not equal it eliminates half of the dataset that can’t have the target in and then it repeats until there are no more item to check

  Outperforms linear search in a big dataset
• Searching


  Purpose of a search algorithm is to see if a target item exists in a data set
• Sorting


  To put a dataset into order

  Typical ordering is ascending or descending numerical or alphabetical