Quick Sort
두비니
·2023. 7. 5. 23:47
Quick Sort
0. 개요
Quick Sort는 특이하게도 Worst case로 따지자면 Merge Sort, Heap Sort보다 안좋은 성능을 보인다. 그러나 Runtime의 기댓값이 낮기 때문에 많이 사용하는 알고리즘이다.
후에도 언급하겠지만 이 핵심은 partition을 어떻게 정하느냐에 있고, 추후 글에는 randomized quick sort에 대해서도 다룰 것이다.
1. Pseudocode
Quicksort는 partition을 정한 뒤,
참고: https://www.youtube.com/watch?v=COk73cpQbFQ
2. Randomized Quick Sort
2.1 Randomized Quick Sort Time Complexity
O(nlgn)
'Coding_Algorithm > DS_Algorithm' 카테고리의 다른 글
| Adjacency Matrix and Adjacency Lists (0) | 2023.07.18 |
|---|---|
| Hash Table/Algorithm and Collision Resolution (0) | 2023.07.17 |
| Heap Sort (0) | 2023.07.04 |
| Probabilistic Analysis (0) | 2023.07.01 |
| Growth of Function (0) | 2023.06.30 |
