2.3.3 Sorting Algorithms

• Bubble sort makes comparison and swaps between pairs of elements. The largest unsorted element is said to 'bubble' to the top of the data, with each iteration.
• This code is an example of bubble sort

  Identify the lines where the swaps are made: 6, 7 ,8

  Identify the time complexity and what line it takes place: o(n^2)

  
• Go through bubble sort:

  1. 4, 1, 9, 6, 7
  2. 4, 1, 6, 9, 7
  3. 4, 1, 6, 7, 9
  4. 1, 4, 6, 7, 9

  
• This bubble sort code has been modified so that it does not make an unnecessary second pass. The program terminates when all swaps have been made.

  
• Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration
• Insertion sort starts at the second element in the input, and compares it to the element to its left. If the two elements are in the wrong order, the smaller element is placed in the lowest position
• This code is an example of insertion sort

  There are two loops within this code in line 3 and line 6. Therefore the time complexity would be o(n^2).

  
• This code is an example of insertion sort. It starts at the second element which would be 9 then.

  1. 4, 1 , 9, 6, 7 and we know the variable will keep moving left so it does not stop till 1, 4, 9, 6, 7
  2. The variable switches to the number 6 then it will become to 1, 4, 6, 9, 7.
  3. Finally the new variable will switch to the number 7 so the new list will be 1, 4, 6, 7, 9

  
• Merge sort is an example of a divide and conquer algorithm.
• A merge sort uses a technique called divide and conquer. The list is repeatedly divided into two until all the elements are separated individually. Pairs of elements are then compared, placed into order and combined.

  
• Perform Merge sort on this.

  1. It first splits into pairs into first 7,4 and 2,6
  2. Then split it individually into 7 and 4 and 2 and 6
  3. Then swap it in lowest to biggest 4, 7 and 2, 6
  4. Finally you can arrange it into 2, 4, 6, 7

  
• Quick sort works by selecting an element, often the central element (called a pivot). Elements smaller than the pivot are placed in a list to the left of the pivot and others are placed in a list to the right
• 1. 4, 3, 1, 5, 2, 6, 9, 7, 8 left pointers being on 4,9 right pointers on 2,8.
  2. 2, 3, 1, 5, 4, 6, 8, 7, 9 left pointers being on 7,5 right pointers on 2,8.
  3. 2, 3, 1, 5, 4, 6, 7, 8, 9 left pointers being on 8,1 right pointers on 2,8. Therefore 8 is a new pivot value.
  4. 1, 3 ,2, 5, 4, 6, 7, 8, 9 left pointer being on 3 right pointer being on 2.
  5. 1, 2, 3, 5, 4, 6, 7, 8, 9 a new pivot value is made at 3, so a new list is created with 3, 5, 4
  6. 1, 2, 3, 4, 5, 6, 7, 8, 9


  Complete this quick sort

  
• Quick sort works by placing elements smaller than the pivot to the left and elements bigger than the pivot to the right
• Quick sort works by placing elements smaller than the pivot to the left and elements bigger than the pivot to the right
• merge sorts worst case, best case, average case is o(log n)