퀵 정렬

예제

퀵정렬의 간단한 설명
퀵정렬은 임의의 pivot 값을 기준으로 pivot 의 좌측에는 pivot 보다 작은값을 두고 우측에는 pivot 보다 큰 값을 두고자 한다.
이 행위는 pivot을 기준으로 좌 우로 이분화 된 리스트를 재귀적으로 반복했을 때 결국 정렬이 완성 된다는 방법 론이다.
보다 쉽게 설명하면 pivot보다 큰 값을 pivot index 보다 왼쪽에서 찾고 ( 큰 값 이 나타날 때까지 i index 를 증가시키도록 한다.)
pivot 보다 작은 값을 pivot index 보다 오른쪽에서 찾는다 ( 작은 값이 나타날 때까지 j index를 감소시키도록 한다. )
pivot을 기준으로 값 비교가 완료되었다면 index 결과 i , j 를 비교 해본다.
i 값이 j 값 보다 작거나 같다면 분명 pivot 을 기준으로 교환을 해야할 값이 있다는 뜻이 된다.
교환한 뒤 i 인덱스는 증가 j 인덱스는 감소 연산을 수행한다.
i 인덱스가 j 인덱스보다 작거나 같다면 계속 반복해서 수행한다.
위 와 같은 과정은 pivot을 기준으로 왼쪽으로 정렬된 list 에서는 최초 Left 값이 감소된 j 보다 작다면 계속 재귀하면되고,
pivot을 기준으로 오른쪽으로 정렬된 list 에서는 최초 Right 값이 증가된 i 값보다 크다면 계속 재귀하면된다.
 ---------------------------------------------------------------------------------------------------------------------------------------------------------
피벗은 p, 리스트 왼쪽 끝과 오른쪽 끝에서 시작한 인덱스들을 i,j라고 하자.
5 - 3 - 7 - 6 - 2 - 1 - 4 
                        p 
리스트 왼쪽에 있는 i 위치의 값이 피벗 값보다 크고, 오른쪽에 있는 j 위치의 값은 피벗 값보다 작으므로 둘을 교환한다.
5 - 3 - 7 - 6 - 2 - 1 - 4 
i                   j   p 
1 - 3 - 7 - 6 - 2 - 5 - 4 
i                   j   p 
j 위치의 값이 피벗 값보다 작지만, i 위치의 값도 피벗값보다 작으므로 교환하지 않는다.
1 - 3 - 7 - 6 - 2 - 5 - 4 
    i           j       p 
i위치를 피벗 값보다 큰 값이 나올 때 까지 진행해 j 위치의 값과 교환한다.
1 - 3 - 7 - 6 - 2 - 5 - 4 
        i       j       p 
1 - 3 - 2 - 6 - 7 - 5 - 4 
        i       j       p 
i위치가 j 위치보다 커지면, i 위치의 값과 피벗 값을 교환한다.
1 - 3 - 2 - 6 - 7 - 5 - 4 
                        p 
1 - 3 - 2 - 4 - 7 - 5 - 6 
            p             
피벗 값 좌우의 리스트에 대해 각각 퀵 정렬을 재귀적으로 수행한다.
1 - 3 - 2       7 - 5 - 6
1 - 2 - 3       5 - 6 - 7
완성된 리스트는 다음과 같다.
1 - 2 - 3 - 4 - 5 - 6 - 7

의사 코드와 세부 설명

function quicksort(q)
      var list less, pivotList, greater
      if length(q) ≤ 1  then
          return q
      select a pivot value pivot from q
      for each x in q except the pivot element
          if x < pivot then add x to less
          if x ≥ pivot then add x to greater
      add pivot to pivotList
      return concatenate(quicksort(less), pivotList, quicksort(greater))
그러나 위 코드는 두 개의 작은 리스트를 저장하기 위해 Ω(n) 크기의 저장공간이 따로 필요하다는 단점이 있다. 실제 구현에서 임시 메모리는 캐시 성능과 속도에 심각한 저하를 가져올 수 있다. 아래와 같이 추가 메모리 없이 배열 내부에서 분할 작업을 구현하면 좀 더 복잡하지만 추가 메모리를 사용하지 않고 구현할 수 있다.
  function partition(a, left, right, pivotIndex)
      pivotValue := a[pivotIndex]
      swap(a[pivotIndex], a[right]) // 피벗을 끝으로 옮겨 놓는다.
      storeIndex := left
      for i from left to right-1
          if a[i] <= pivotValue then
              swap(a[storeIndex], a[i])
              storeIndex := storeIndex + 1
      swap(a[right], a[storeIndex]) // 피벗을 두 리스트 사이에 위치시킨다.
      return storeIndex
이것은 내부 분할 알고리즘이다. 이 알고리즘은 주어진 배열에서 pivotIndex에 위치한 값보다 작은 값들을 리스트의 앞쪽에, 큰 값들을 리스트의 맨 뒤에 몰아넣음으로써 left와 right 위치 사이의 원소들을 두 개로 분할한다. 그리고 그렇게 분할된 두 리스트 사이에 피벗을 위치시키면 피벗의 위치가 정해진다. 또한 피벗 값은 임시로 리스트의 맨 뒤에 저장해놓기 때문에 중간에 피벗의 위치가 바뀌거나 하지 않는다.
이렇게 분할 알고리즘을 구현하면 퀵 정렬은 다음과 같이 간단하게 구현할 수 있다.
  function quicksort(a, left, right)
      if right > left then
          select a pivot value a[pivotIndex]
          pivotNewIndex := partition(a, left, right, pivotIndex)
          quicksort(a, left, pivotNewIndex-1)
          quicksort(a, pivotNewIndex+1, right)
Pascal과 C와 같은 명령형 언어에서는 대부분 이와 같은 내부 분할을 이용해 구현한다.

개선된 피벗 선택

퀵 정렬에서 피벗 위치를 결정하는 방법에는 여러가지 방법이 있다. 기초적인 방법으로는 난수 분할이 사용되는데, 안정성이 떨어진다. 많은 라이브러리에서는 세 값(좌측 끝, 중앙, 우측 끝)의 중위법을 이용하여 분할한다. 이 방법을 사용하면 중앙에서 분할될 가능성이 높아 전체적으로 정렬의 성능이 좋아진다.

C

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int pivot = arr[(left + right) / 2];
      int temp;
      do
      {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i<= j)
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
      } while (i<= j);

    /* recursion */
    if (left < j)
        quickSort(arr, left, j);

    if (i < right)
        quickSort(arr, i, right);}

C++

inline void swap(int &a, int &b){
    int t = a; a = b; b = t;}void quickSort(int A[], int low, int high) {
    if(low >= high) return; // base condition

    // divide process
    int i = low-1, j = low;
    int&pivot = A[high];
    for (; j < high; ++j) {
        if ( A[j] < pivot)
            swap(A[++i], A[j]);
    }
    swap(A[++i], pivot);

    // conquer process
    quickSort(A, low, i-1);
    quickSort(A, i+1, high);}

java

public void quickSort(int[] arr, int left, int right) {
    int i, j, pivot, tmp;
    if (left < right) {
        i = left;   j = right;
        pivot = arr[(left+right)/2];
        //분할 과정
        while (i < j) {
            while (arr[j] > pivot) j--;
            // 이 부분에서 arr[j-1]에 접근해서 익셉션 발생가능함.
            while (i < j && arr[i] < pivot) i++;

            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        //정렬 과정
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }}

비주얼 베이직

Private Function QR(a() As Long, left As Long, right As Long)Dim pivot, left_hold, right_hold As Longleft_hold = leftright_hold = rightpivot = a(left)Do While (left < right)Do While ((a(right) >= pivot) And (left < right))right = right - 1LoopIf left <> right Thena(left) = a(right)End IfDo While ((a(left) <= pivot) And (left < right))left = left + 1LoopIf left <> right Thena(right) = a(left)right = right - 1End IfLoopa(left) = pivotpivot = leftleft = left_holdright = right_holdIf left < pivot ThenCall QR(a(), left, pivot - 1)End IfIf right > pivot ThenCall QR(a(), pivot + 1, right)End IfEnd FunctionPrivate Function QS(a() As Long, count As Long)Call QR(a(), 0, count - 1)End Function

OCaml

let rec quicksort = function
   | [] -> []
   | pivot :: rest ->
       let is_less x = x < pivot in
       let left, right = List.partition is_less rest in
       quicksort left @ [pivot] @ quicksort right

하스켈

quicksort [] = []quicksort (p:tl) = quicksort [ x | x <- tl, x <= p ] ++ [p] ++ quicksort [ x | x <- tl, x > p ]
OCaml 과 비교를 쉽게하기 위한 version
quicksort [] = []quicksort (pivot:rest) =
let left = [x| x <- rest, x <= pivot]
 right = [x| x <- rest, x > pivot]
        in quicksort left ++ [pivot] ++ quicksort right

파이썬

1 def quicksort(x): 2     if len(x) <= 1: 3         return x 4  5     pivot = x[len(x) // 2] 6     less = [] 7     more = [] 8     equal = [] 9     for a in x:10         if a < pivot:11             less.append(a)12         elif a > pivot:13             more.append(a)14         else:15             equal.append(a)16 17     return quicksort(less) + equal + quicksort(more)

파이썬 (Cache 없이)

1 def partition(arr, start, end): 2     pivot = arr[start] 3     left = start + 1 4     right = end 5     done = False 6     while not done: 7         while left <= right and arr[left] <= pivot: 8             left += 1 9         while left <= right and pivot <= arr[right]:10             right -= 111         if right < left:12             done = True13         else:14             arr[left], arr[right] = arr[right], arr[left]15     arr[start], arr[right] = arr[right], arr[start]16     return right17 18 19 def quick_sort(arr, start, end):20     if start < end:21         pivot = partition(arr, start, end)22         quick_sort(arr, start, pivot - 1)23         quick_sort(arr, pivot + 1, end)24     return arr

스칼라

def quickSort(arr:Array[Int]):Array[Int] = {

   if (arr.length <= 1) return arr

   val pivot = arr(arr.length / 2)

   var left, right, equal = Array[Int]()

   for (a <- arr) {
      if (a < pivot) left = left :+ a
      else if (a > pivot) right = right :+ a
      else equal = equal :+ a
   }

   quickSort(left) ++ equal ++ quickSort(right)

  }