Sorting
Top K problem
Optimization progress:
Regular sorting: O(NlogN)
Priority Queue: O(NlogK)
QuickSelect: O(N) average with shuffle. still O(N^2) in worst case though.
Bucket sort: O(N)
Randomization
Shuffle
private void shuffle(int nums[]) {
final Random random = new Random();
for (int i = nums.length - 1; i >= 0; i--) {
int j = random.nextInt(i+1);
exchange(nums, j, i);
}
}
Reservoir sampling
Explain: https://www.youtube.com/watch?v=A1iwzSew5QY
Proof:
For k+i, the probability that it is selected and will replace a number in the reservoir is k/(k+i)
For a number in the reservoir before (let’s say X), the probability that it keeps staying in the reservoir is
P(X was in the reservoir last time) × P(X is not replaced by k+i)
= P(X was in the reservoir last time) × (1 - P(k+i is selected and replaces X))
= k/(k+i-1) × (1 - k/(k+i) × 1/k)
= k/(k+i)
When k+i reaches n, the probability of each number staying in the reservoir is k/n
Sorting in linkedlist
merge sort: https://leetcode.com/problems/sort-list
selection sort: https://leetcode.com/problems/insertion-sort-list/description/
Summary

Merge Sort


Quick Sort


Bubble Sort

Selection Sort

Insertion Sort

Heap Sort
https://www.geeksforgeeks.org/heap-sort/
Array
represent aheap
(Complete Binary Tree) : root i, left 2i+1, right 2i+2;heapify
the heap, make itmaxHeap
swap root and last one, therefore 'remove' largest to the array tail
heapify
the rest
Shell Sort

Bucket Sort
https://leetcode.com/problems/top-k-frequent-elements/description/ https://leetcode.com/problems/top-k-frequent-words/description/
special sorting
counting sort: https://leetcode.com/problems/sort-colors/description/
partition sort: part of Quick Sort, https://leetcode.com/problems/kth-largest-element-in-an-array/description/
Reference
https://www.toptal.com/developers/sorting-algorithms

Last updated
Was this helpful?