Quick Sort: 퀵 정렬

 

* Quick Sort?

퀵 정렬도 합병 정렬과 같이 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵 정렬하는 분할정복법에 근거한다. 그러나 합병 정렬은 전체 데이터를 n/2로 나눴던 것과 달리, 퀵소트는 비균등하게 분할한다. 리스트 안에 있는 한 요소를 기준(피봇(pivot))으로 선택한다. 피봇을 중심으로 왼쪽은 피봇보다 작은 요소들로 옮겨지고, 오른쪽은 피봇보다 큰 요소들로 재구성되게 된다. 이 상태에서 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트를 재정렬하게 되면 전체 리스트가 정렬된다.

퀵 정렬 함수는 부분 리스트에 대하여 순환 호출 된다. 부분 리스트들이 더 이상 분할이 가능할 때까지 피봇을 기준으로 2개의 부분 리스트로 재분할되는 것이다.  

 

이미지 출처  https://prepinsta.com/c-program/quick-sort/

그러니까 퀵 소트는 피봇을 골라서, 피봇보다 작은 거는 왼쪽으로 큰 거는 오른쪽으로 바꾼다는 것이 핵심이다. 

* Pseudocode

 

* 분석

n이 2의 거듭제곱이라고 가정하고 만약에 큌 정렬에서 리스트 분할이 항상 리스트의 가운데에서 이루어진다고 가정하면 합병 정렬의 복잡도 분석과 마찬가지로 n개의 레코드를 가지는 리스트는 n/2, n/4, n/8,,, n/2^k가 되고 k는 log2n되며 총 n번 비교해야 하므로 비교 횟수는 nlog2n이 되고, 이동횟수는 비교횟수보다 작기 때문에 무시할 수 있어서 총 퀵 소트의 시간복잡도는 O(nlog2n)이 된다.

그러나 최악의 경우 리스트가 계속 불균형하게 나누어지면 패스의 개수는 n이 되고, 한번의 패스에서 평균 n번 정도의 비교 연산이 필요하므로 거의 O(n^2)의 시간복잡도가 된다. 즉 최악의 경우 O(n^2)의 시간 복잡도를 가지게 되는 것이다. 

퀵 정렬의 장점은 대량의 데이터를 정렬할 때 유리하다는 것이며, 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는 등의 장점이 있다.

단점으로는 이미 거의 정렬된 리스트에 대해서는 오히려 수행시간이 더 많이 걸린다는 단점도 있다. 이러한 불균형 분할을 방지하기 위해 피벗을 선택할 때 리스트의 중앙 부분을 분할할 수 있는 데이터를 선택하여 중간값을 피벗으로 사용하는 것이다. 

 

퀵 정렬의 평균적 시간 복잡도: O(nlog2n)

최악의 경우 시간 복잡도: O(n^2)