Quick Sort
[Divide and Conquer paradigm](https://texonom.com/divide-and-conquer-paradigm-9b10e85e70214b9b8f0bd293f5c297bd) 


### Very practical but worst case is $O(n^2)$
**Many languages use this as default sort algorithm.**
Quick sort is typically over twice faster as merge sort. It is [In-place sort](https://texonom.com/in-place-sort-c90e8ba56ded483f907bbe5a663045a6) so we need memory allocation and free memory process). There is only swapping in quick sort which are supported by [Register](https://texonom.com/register-060d7a6c16ca4a89aa5ebbafbc01a9f1) hardware. event theoretically merge sort is better. Quick sort access sequentially so more suitable for modern computer compared to randomly accessing merge sort.


### Algorithm
![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2Faaaadf4e-a547-4622-adf9-da8c3308aec1%2FUntitled.png?table=block&id=8a54b9eb-94af-4dfb-9aa6-6df91527a7e4&cache=v2)
trivially no merge step for combining ‣ 
![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2F0ad0acea-6bff-48b7-9aed-140b1e355104%2FUntitled.png?table=block&id=e1439105-cfa5-4cb3-a6db-9516ffae915f&cache=v2)
### Key part is this divide (partition) step
![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2Fe3944dca-caa1-49f5-abd1-a43326c7dd3b%2FUntitled.png?table=block&id=3ea1ece3-c457-4a97-b58b-42f3e853cb80&cache=v2)
쉽게 설명하면 첫번째 걸로 전체 작은거 큰거 나눈 다음에 나눠진 거에서 다시 크고 작은거로 나눠가기 그래서 worst case is bad (partition is around min or max element) but complexity is $O(n^2)$ only when sorted or reverse
![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2F1c37895b-ee98-4077-a294-c716d2ebfd59%2FUntitled.png?table=block&id=8c24d153-6805-4e0e-9bf4-b863fb0cd233&cache=v2)


### Introducing Randomness
If we introduce random pivot, sorted or reversed is not worst case
every recursion, we use each independent pivot selection
which means probability of each partition is random (with [Indicator random variable](https://texonom.com/indicator-random-variable-cac27017b7ba4e0db0242d305884e37d) $X$)
> ![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2F8d9d8f00-9fe6-4d1a-a251-ec196c68b7f8%2FUntitled.png?table=block&id=077bf55a-6f01-4581-8d65-5bc781e0ee49&cache=v2)
> ![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2F29e55d44-27ca-4d0b-b1fa-1e9997626ae8%2FUntitled.png?table=block&id=97b4dbf5-10e2-4b08-939d-1c271151f2d8&cache=v2)
And using mathematical induction (using mathematical fact)
first equation is [Inductive hypothesis](https://texonom.com/inductive-hypothesis-b8850c425fc44b1d9a174debdc98ecd5) 
> ![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2Fddaa92f1-1c2a-48b4-9b69-05c7d564494a%2FUntitled.png?table=block&id=80cdf581-2f27-4a82-99e9-8f6a3705a11c&cache=v2)
> ![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2Ff197bacf-204b-48be-a12b-2b36b22bc78f%2FUntitled.png?table=block&id=0cf2d14a-fa15-4253-9928-2dcf1d605e0b&cache=v2)
> ![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2F4f90be01-7d39-4dd4-9999-a58a41c583db%2FUntitled.png?table=block&id=e176ee5f-ba3c-4166-9a7f-cf5089ccf193&cache=v2)
For n possible scenarios, the expected runtime is $nlogn$





