01:198:107 Lecture Notes - Lecture 15: Selection Sort, Insertion Sort, Quicksort
27 Apr 2018
School
Department
Course
Professor
CS 107: Lecture 15: Real Numbers
● Sorting
○ Insertion sort
○ Selection sort
○ Quick sort
○ Merge sort
○ Many others
● In place insertion sort
○ We don’t really need two vectors, unsorted and sorted - we can keep all
the data in one vector
● How much work is it?
○ Length^2 is worst case
○ We might find the right place early
○ If vector already close to sorted, takes much less than length^2
○ Note the cost of moving things in addition to comparing
● Selection sort
○ Find smallest in unsorted
○ Move it to end of sorted
● In place selection sort
○ Key idea: swap smallest unsorted and first unsorted
● Selection vs Insertion
○ Selection sort
■ Simpler to write
■ Same worst case: O(n^2)
■ Cannot make use of partial pre-sorting: worse average case
○ Insertion sort
■ Harder (but still simple) to write
■ Same worse case: O(n^2)
■ Can make use of partially sorted list: better average case
● Quick sort
○ Divide and conquer
Document Summary
We don"t really need two vectors, unsorted and sorted - we can keep all the data in one vector. We might find the right place early. If vector already close to sorted, takes much less than length^2. Note the cost of moving things in addition to comparing. Key idea: swap smallest unsorted and first unsorted. Cannot make use of partial pre-sorting: worse average case. Can make use of partially sorted list: better average case. Groups are number > pivot, < pivot. Scan from small indexes looking for a number > pivot. Scan from large indexes looking for a number < pivot. Assuming each split is into halves: log(n) sizes. If pieces are of size k we have n/k of them. Work to split or join pieces is proportional to size of the piece. For quicksort we assumed each split was in halves, but this depends on pivot. Nothing more about merge sort on tests.
