Elvin Yung
- We previously discussed quick select, which was a method to select the kth item in some sorted array.
- Quick select has an expected linear running time. Since the input size halves every time, the overall amount of work done for some input of size
nis roughlyn + (n/2) + (n+4) + ... = 2n.
- Suppose that we have some unsorted array, and we want to return the top
kelements. - We could heapify the array and retrieve the top
kelements, but an even better solution is to use quick select. - This runs at roughly Ө(n + k log k).
- In the in-place implementation of quicksort, keep swapping the outermost wrongly-positioned pairs around the pivot.
- Is it possible to sort in O(n)? It depends.
- It depends on what you're sorting, and what you're allowed to do with the data.
- For example, if you have a permutation of
1..n, then just replace the collection with [1..n]. - In most cases, to sort at O(n) or lower, it takes some clever tricks.
- *Comparison sorting is when you attempt to sort a set of objects that are comparable to each other.
- Theorem: Any comparison-based sort takes Ω(n log n) to sort n "priviate" items.
- Let π be a permutation of 1..n.
- sort(π) = (π^-1)(π)
- In other words, sorting is the inverse of a shuffling permutation.
- Then we can think of every comparison in a sorting algorithm as the process of recovering the perutation applied to the sorted input.