[Quick Sort] Quick sort는 왜 빠를까? (1) : Randomized 된 Quicksort / Quick sort의 Worst running time (최악)

Quick Sort란?

피벗을 중심으로 작은쪽, 큰쪽으로 나누어 정렬하는 방식을 뜻한다.

메모리 소비가 없고 무엇보다 정렬속도가 빠르기 때문에 Quick sort로 이름이 붙여졌다.

(* 참고 : https://coderkoo.tistory.com/7)

 

Quick Sort의 시간복잡도

허나 다들 알다시피 Quick Sort의 시간복잡도는 O(n^2) ,Ω(n lgn) 이다. (이는 구글에 검색해보면 자료가 많으니 생략, 아까 링크한 블로그에 자세히 설명이 되어있다!)

최악과 최적 모두 Θ(n lgn) 인 Heap Sort와 Merge Sort 에 비하면 겉보기에는 느릴 수 있어보인다.

그렇다면 왜 Quick Sort는 Quick Sort 인 것일까?

 

Randomized 된 Quicksort의 최악은?

우리가 정렬을 이용할 때, 대부분의 경우의 input case는 Random성을 가진 (무작위의) 인풋들이 대부분일 것이다.

따라서, 우리는 이러한 무작위성의 성질을 고려하며 Running Time 을 계산할 필요가 있다.

 

그렇다면 Randomized 버전의 퀵소트의 최악의 경우는 어떠할까???

---

퀵소트의 점화식은 피벗으로 설정된 값 하나의 값에 따라 달라진다.

T(L) : [피벗으로 설정된 값보다 작은 값들의 배열]

T(R) : [피벗으로 설정된 값보다 큰 값들의 배열]  

T(n) = T(L) + T(R) + Θ(𝑛) 이라 표현 할 수 있다.

여기서 L 과 R 들은 n보다 작은 어떠한 수라고 할 수 있으므로

랜더마이즈된 값의 최악은 피벗값을 제외한 나머지 배열 점화식 + Θ(𝑛) 의 합인

T(n) = max (0≤𝑞≤𝑛−1) (T(q) + T(n−q−1))+ Θ(𝑛))

 

인데 이를 Substitution method 로 시간복잡도를 알아보면 (T(n) = cn^2 로 놓고 계산하면 나옴)

결국 T(n) = O(𝑛^2) 이 나온다.

---

엥? 랜덤한 상황에서도 최악의 경우는 계속해서 O(𝑛^2) 이 나오니 퀵소트가 왜 좋은 것인지 당최 알 수 가 없다.

 

이것은 바로 우리가 기대값의 개념을 생각하지 않았기 때문이다.

 

기대값을 고려하여 계산하는 방법은

다음 게시글 ( QuickSort는 왜 빠를까? (2) :Expected Running Time https://programming119.tistory.com/56 )

에서 이어진다..

 

* 참고 : 고려대학교 정순영 교수님 알고리즘 강의

---

 

냐냐냐냐냐ㅑ냐냐냥