[알고리즘] 더 효율적인 Quick Sort에 대한 생각

오늘 학기의 마지막 자료구조론 수업으로 Sort 알고리즘들에 대해 배웠다.

 

그 중 Quick Sort를 더 효율적인 Time Complexity로 사용할 수 있을 것 같아 생각을 글로 남긴다.

 

먼저 Selection Sort, Insertion Sort, Bubble Sort와 같은 경우 O(n^2)의 Time Complexity를 갖는다.

 

그리고 Merge Sort, Quick Sort의 경우 O(nlogn)의 Time Complexity를 갖는다.

 

근데 Quick Sort는 조금 다른점이 있는데 다른 Sort 알고리즘의 경우 worst case의 Time Complexity이지만 Quick Sort는 평균적인 경우의 Time Complexity였다.

 

Quick Sort는 pivot을 결정하는 부분에서 variation이 있을 수 있는데 기본적인 Quick Sort 알고리즘은 이 pivot을 랜덤하게 선택한다.

 

편향된 트리(skewed tree)

때문에 pivot이 운안좋게 계속 전체 배열의 가장 큰 값이나 작은 값을 선택한다면 위와 같은 편향된 트리가 만들어져 worst case가 발생하는 것이다. O(n^2)

 

이 내용을 들으면서 이 pivot을 선택하는 과정에서 pivot을 항상 배열 element들의 중앙값으로 선택하면 worst case에도 O(nlogn)을 가지지 않을까라는 생각을 했다.

 

어차피 배열의 elements에서 중앙값을 구하는 과정도 for문 하나만 쓰면 되기 때문에 O(n)이고 O(n)+O(nlogn)=O(nlogn)이기 때문이다.

이렇게 pivot을 선택하면 언제나 Full Tree에 가까운 트리가 만들어져 효율적일 것이다.

결국 트리의 높이가 중요하기 때문이다.

 

full tree

 

 

---

 

 

 

물론 pivot은 랜덤하게 선택하기에 worst case가 발생할 확률이 무척 낮다는 것을 안다.

하지만 배열의 elements가 무척 많은 경우, 알고리즘의 속도가 중요한 경우에 좀더 효율적인 솔루션을 줄 수 있을 것으로 생각된다.