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

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

### 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](https://jaywin.gitbook.io/leetcode/solutions/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](https://jaywin.gitbook.io/leetcode/solutions/0398-random-pick-index)
* [0382. Linked List Random Node](https://jaywin.gitbook.io/leetcode/solutions/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

![](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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/topics/sorting.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.