Quick Sort

퀵소트 알고리듬

퀵소트는 임의의 값을 골라 이를 피봇으로 잡고 피봇보다 작은 값은 피봇의 왼쪽, 큰 값은 피봇의 오른쪽으로 배치한 후, 다시 피봇을 기준으로 나눈 좌, 우의 부분집합을 퀵소트로 배열해 나가는 정렬방법이다.

  1. 결국 배열, 시작위치, 끝 위치를 필요로 한다.
  2. 시작위치가 끝위치와 같거나 크면(클 일은 사실 없음) 이미 정렬된 상태로 간주한다.
  3. 첫 위치가 피봇이 된다.
  4. 첫 위치의 다음 인덱스가 left, 끝 위치는 right 가 된다.
  5. left는 피봇값보다 큰 값을 발견할 때까지 증가 (혹은 배열의 끝 위치)
  6. right는 피봇값보다 작은 값을 발견할 때까지 감소 (혹은 피봇값의 바로 다음 위치까지)
  7. 5, 6을 수행한 후 두 마크가 만나지 않았다면, 두 마크 간의 값을 교환한다. 그리고 5, 6을 계속 진행한다.
  8. 만약 교차가 일어났다면 즉 right 마크의 인덱스값이 left 마크보다 작다면? right마크와 피봇의 값을 교환한다.
  9. 이제 0 ..> 피봇, 피봇 <.. 끝 까지의 범위에 대해 각각 퀵 소트를 시전한다. 이 재귀 알고리듬은 2를 베이스로하면서 종료하게 된다.

간단히 말해 피봇값을 정하고, 피봇값보다 큰 값과 작은 값으로 구분한 다음에 피봇값을 그 사이에 딱 박아넣어서 간략한 정렬을 하고 이를 쪼개어 적용한다는 뜻이다.

준비한 예제를 따라 위 알고리듬을 적용해보자.

[45][53][26][93][62][20][33][17]
~~~~ ^>                      <^

먼저 첫 원소 45를 피봇으로 한다. 그 다음 위치와 배열의 끝에 left 마크와 right 마크가 존재한다. 먼저 left마크는 해당 인덱스의 값이 피봇값보다 클 때까지 우측으로 이동, right는 반대로 피봇값보다 작은 값을 찾아 왼쪽으로 이동한다.

[45][53][26][93][62][20][33][17]
 ~~  *>                      <*  

일단 이동을 해보기도 전에 left, right는 각각 정지하게 된다. (둘 다 조건에 안맞는 값임) 두 마크가 교차하기 전이므로 이 마크의 값들을 교환한다.

[45][17][26][93][62][20][33][53]
 ~~  *>                      <*  

그리고 다음 값을 찾아서 출발~

 [45][17][26][93][62][20][33][53]
  ~~          *>               <*

먼저 left마크는 93을 찾았다.

[45][17][26][93][62][20][33][53]
~~          *>          <* 

그리고 right마크는 33을 찾았다. 둘을 교환하고 계속 진행한다.

[45][17][26][33][62][20][93][53]
 ~~              *>  <*

그리고 다음, 62, 20에서 각각 마크가 멈췄다. 값 교환후 진행

[45][17][26][33][20][62][93][53]
 ~~              <*  *>

left는 다시 62(교환된 후의 위치)에 도달했고, right는 20(교환된 후의 위치)에 도달했다. 이 때, right 마크의 인덱스는 left 인덱스보다 작으므로 두 마크가 교차했음을 알 수 있다. 즉, 지금 right 마크의 위치는 피봇값보다 작은 값 중 가장 오른쪽에 있는 값이다.

[20][17][26][33][45][62][93][53]
                 ~~ 

그래서 오른쪽 마크에 있는 값과 피봇값을 교환했다. 이제 피봇을 중심으로 피봇보다 작은 값은 왼쪽, 큰 값은 오른쪽에 있다.

________________
[20][17][26][33]|[45]|[62][93][53]
 ^^  *>      <*      

피봇보다 작은 부분 배열에 대해서 동일한 퀵소트를 적용한다. 이번에는 20이 피봇값이고, 17과 33에서 각각의 마크가 출발한다.

[20][17][26][33]|[45]|[62][93][53]
 ^^  <*  *>    

각 마크가 멈춘 위치는 위와 같다. 피봇과 right 마크의 값을 교환

 __   
[17][20][26][33][45]|[62][93][53]

20의 왼쪽에 있는 부분 배열은 1개의 원소만을 가지므로 이미 정렬됐다고 판단.

        ________     
[17][20][26][33][45][62][93][53]
         **  <>

20의 우측 부분 집합은 두 마크의 위치가 동일한 지점에서 시작하고 더 이상 움직일 수 없다.
교차했다고 판단하고 종료한다.

이제 첫 피보팅 이후의 오른쪽에 대해서도 동일한 방법으로

                     ____________
[17][20][26][33][45][62][93][53]
                     ^^  *>  <*

교환

[17][20][26][33][45][62][53][93]
                     ^^  *>  <*

그리고 곧 다음 턴에서 마크는 교차하고, 피봇 위치와 교환

[17][20][26][33][45][53][62][93]

이로써 정렬이 끝났다.

다음은 퀵소트를 구현한 코드이다.

def quickSortHelper(alist, first, last):
    if first < last:
        pivotValue = alist[first]
        leftmark = first + 1
        rightmark = last
        crossed = False
        while not crossed:
            while alist[leftmark] <= pivotValue and leftmark < rightmark:
                leftmark += 1
            while alist[rightmark] >= pivotValue and rightmark > first:
                rightmark -= 1
            if leftmark < rightmark:
                crossed = False
                alist[leftmark], alist[rightmark] = alist[rightmark], alist[leftmark]
            else:
                crossed = True

        alist[first], alist[rightmark] = alist[rightmark], alist[first]
        quickSortHelper(alist, first, rightmark - 1)
        quickSortHelper(alist, leftmark, last)

def quickSort(alist):
    quickSortHelper(alist, 0, len(alist) - 1)

퀵소트의 효율은 \(O(n log _n)\)이지만 평균적인 성능은 다른 비슷한 O노테이션 값을 가지는 정렬알고리듬에 비해 우수하다. 왜냐하면 퀵소트는 병합정렬등과 달리 서브 리스트를 생성하는 과정이 없는 제자리 정렬이기 때문이다. 하지만 이미 정렬된 배열에 대해 퀵소트를 적용하는 것은 최악의 성능을 내게 된다. 이러한 극단적인 상황에서의 성능을 향상시키기 위해서는 피봇값을 맨 첫 값이 아닌 중간값을 사용하도록 하는 등 다른 개선 방안들이 있다.

제자리 정렬중에서 가장 괜찮은 평균성능을 보여주고 있어서 퀵소트는 널리 쓰이는 알고리듬 중 하나이며, C의 표준 라이브러리에서도 퀵소트 함수를 제공한다.