Quick Sort

 

 

 

---

Quick Sort

---

 

 

 

 

 

0. 개요

 

Quick Sort는 특이하게도 Worst case로 따지자면 Merge Sort, Heap Sort보다 안좋은 성능을 보인다. 그러나 Runtime의 기댓값이 낮기 때문에 많이 사용하는 알고리즘이다. 

후에도 언급하겠지만 이 핵심은 partition을 어떻게 정하느냐에 있고, 추후 글에는 randomized quick sort에 대해서도 다룰 것이다.

 

 

 

1. Pseudocode

 

Quicksort는 partition을 정한 뒤, 

 

O(n)

 

 

 

참고: https://www.youtube.com/watch?v=COk73cpQbFQ 

 

 

 

2. Randomized Quick Sort

 

 

 

 

2.1 Randomized Quick Sort Time Complexity

 

O(nlgn)