Quick Sort(퀵 정렬) 에서의 Pivot 선택

(http://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot)

 

퀵 정렬에서의 피봇 선택에 따라서,

 

퀵 정렬의 실행 시간은 O(NlgN)에서 최대 O(N^2) 까지 걸릴 수 있다.

 

 

 

 

나쁜 (worst-case)의 경우의 예를 들면,

 

- 이미 정렬이 되어 있는 배열 (또는 거의 정렬된 배열)

- 반대로 정렬이 되어 있는 배열

 

을 정렬하고자 할 때, pivot을 가장 첫 번째 원소나 가장 마지막 원소로 지정하는 것이다.

 

이 경우, 각 단계마다 '원소 1개'와 '나머지 원소 전부' 로 쪼개지기 때문에,

 

divide-and-conquer 방식의 이점을 살리지 못하게 된다.

 

 

 

효율적인 Quick Sort를 위해서는, pivot을 잘 선택할 필요가 있다.

 

위 글에서 본 방법 중 일부는 다음과 같다.

 

1. Random Pivot    :    말 그대로 랜덤.

2. median - of - three    :    아래와 같은 과정으로 이루어진다.

1) random index 3개를 뽑는다.

2) 이 3개가 가리키는 원소들의 median 값으로 pivot을 설정한다.

 

 

 

이외에도 다양한 pivot 선택 전략이 있는데,

 

input으로 들어오는 배열의 성질에 따라서, 그 전략을 다르게 해야 할 것이다.

 

저 글의 링크에는 좀 더 다양한 토론이 있는데, 보는 것을 추천한다.