COMPSCI 61B Lecture Notes - Lecture 34: Deterministic Algorithm, Quicksort, Royal Institute Of Technology
28 Aug 2017
School
Department
Course
Professor
Document Summary
Tony proposed a scheme where two pointers walk towards each other: * neither likes items of the same value as the pivot. * big idea: walk towards each other, swapping anything they don"t like. * end result is that things on left are small and things on the right are large . Use median of medians" (called pick in original paper) Slower than a partitioning based approach commonly called quickselect. Partition, gure out if pivot is in the position of the median. If not, then partition the correct side and repeat. Worst case performance: (n^2) when the array is already sorted. On average, quick select will take (n) time. A sort is said to be stable if order of equivalent items is preserved. Useful for sorting by two properties (sort by secondary property then primary property) Quick sort may or may not be depending on the partitioning strategy. No stable partitioning strategy that is faster than merge sort exists (probably?)
