2.3.3 Sorting Algorithms

• Quick Sort

  1. First item chose as pivot
  2. Two sub-lists created, those which are less than or equal to pivot and those which are bigger than pivot
  3. Recursively apply 2 steps until all sub-lists are pivots
  4. Pivots now combined to form sorted list
• Quick Sort

  Applies however we would choose the first item as the pivot instead of the last but it doesn't matter

  Time complexity O(n^2)

  
• Merge Sort

  • Divide and conquer
  • Merge sort is formed from two functions. One called MergeSort and another called Merge

  
• Insertion Sort

  Consists of two lists: Sorted and Unsorted

  same time complexity as bubble sort, O(n2)

  • One item at a time
  • Moved into correct position
  • Until all items in list checked

  
• Bubble Sort

  • Compare each pair of adjacent elements
  • If they are not in the correct order then swap the elements
  • If they are in the correct order then do not swap elements
  • When you reach the end of the array return to the start
  • Repeat n elements time
  • Set a flag to be false whenever a swap is made
  • Repeat the loop if the flag is not false