COMP 352 Lecture Notes - Lecture 20: Radix Sort, Quicksort, Merge Sort

• School: Concordia University
• Department: Computer Sci.
• Course: COMP 352
• Professor: T B A

Document Summary

Quick sort, in-place quick sort, hybrid quick sort, bucket- Runs faster than heap sort (based on expected runtime) In this case insertion sort is ideal for small inputs. The sizes of l and g are each less than 3s/4 (similar) There is 1/2 chances of getting a good call. One of l and g has size greater than 3s/4. Move l to the right until you find an element > 6 (pivot) a. b. Move r to the left until you find an element < 6 (pivot) a. b. Repeat process 4 and 5 until the l and r have crossed, then you stop a. b. Now the array will be partitioned into l and upper will be r. You need the whole input at same time. You stop the recursion before the size becomes 1 (reasonable value) Example, when input size becomes 100 commence insertion sort operation. When input size becomes small you apply insertion-sort.