> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/topics/sorting.md).

# 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](/leetcode/topics/sorting.md)
* Bucket sort: O(N)
  * [347-Top K Frequent Elements](/leetcode/topics/sorting.md)

<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)](/leetcode/solutions/0380-insert-delete-getrandom-o1.md)
* [0381. Insert Delete GetRandom O(1) - Duplicates allowed](/leetcode/solutions/0381-insert-delete-getrandom-o1-duplicates-allowed.md)

### Shuffle

[Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle):

```java
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](/leetcode/solutions/0384-shuffle-an-array.md)

### 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](/leetcode/solutions/0398-random-pick-index.md)
* [0382. Linked List Random Node](/leetcode/solutions/0382-linked-list-random-node.md)

## Sorting in linkedlist

merge sort: <https://leetcode.com/problems/sort-list>

selection sort: <https://leetcode.com/problems/insertion-sort-list/description/>

## Summary

![](http://blog.benoitvallon.com/img/2016-03-12-sorting-algorithms-in-javascript/big-o.png)

### Merge Sort

![](http://codepumpkin.com/wp-content/uploads/2017/10/MergeSort_Avg_case.gif) ![](https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/mergesort/pages/merge2.gif)

### Quick Sort

![](https://www.tutorialspoint.com/data_structures_algorithms/images/quick_sort_partition_animation.gif) ![](https://www.w3resource.com/w3r_images/quick-sort-part-1.png)

### Bubble Sort

![](http://codepumpkin.com/wp-content/uploads/2017/10/BubbleSort_Avg_case.gif)

### Selection Sort

![](http://codepumpkin.com/wp-content/uploads/2017/10/SelectionSort_Avg_case.gif)

### Insertion Sort

![](https://upload.wikimedia.org/wikipedia/commons/9/9c/Insertion-sort-example.gif)

### Heap Sort

![](https://upload.wikimedia.org/wikipedia/commons/f/fe/Heap_sort_example.gif) <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

![](http://www.stoimen.com/blog/wp-content/uploads/2012/02/Shell-Sort.png)

### Bucket Sort

<https://leetcode.com/problems/top-k-frequent-elements/description/> <https://leetcode.com/problems/top-k-frequent-words/description/> ![](https://upload.wikimedia.org/wikipedia/commons/thumb/e/e3/Bucket_sort_2.svg/311px-Bucket_sort_2.svg.png)

### 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>

![](http://78.media.tumblr.com/7dded0c741988840259e6140785495d3/tumblr_ohb7nxWBcd1sftw41o1_1280.gif)