CS 2420 Lecture 6: Week 6 In-Depth Sort Analysis, Stacks & Queues
21 Feb 2017
School
Department
Course
Professor
Document Summary
Should be used for nearly sorted data, big o = n for mostly sorted input. Should be used for small sets of data, since it has no recursive calls or extra memory. Quick sort is better than merge sort because: Chooses a cutoff at which recursion stops and insertion sort starts. Chooses pivot as first element, places pivot at the end of the array. Same as first pivot but inclusively selecting random element between start and end. Insertion sort the start, mid, and end element (to find median of 3 elements) Swap pivot (middle of sorted 3 elements) to end - 1, since last element is largest. Swap end - 1 (pivot) and end element to be able to use standard partitioning (which requires pivot to be the last element) Or rewrite partition method to use pivot at end - 1. 2: i as left counter, j as right. Move i to the right until value is larger than pivot.
