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.

  • 215-Kth Largest Element in an Array

• Bucket sort: O(N)

  • 347-Top K Frequent Elements

https://leetcode.com/problems/k-closest-points-to-origin/discuss/220235/Java-Three-solutions-to-this-classical-K-th-problem.

Randomization

• 0380. Insert Delete GetRandom O(1)

• 0381. Insert Delete GetRandom O(1) - Duplicates allowed

Shuffle

Fisher–Yates 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);
    }
}

• 0384. Shuffle an Array

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

• 0398. Random Pick Index

• 0382. Linked List Random Node

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 a heap (Complete Binary Tree) : root i, left 2i+1, right 2i+2;

• heapify the heap, make it maxHeap

• 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