[C] 퀵정렬 개념, 알고리즘, 코드 정리

퀵 정렬

---

찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘입니다.

n 개의 데이터를 정렬할 때 최악의 경우 O(n^2) 번의 비교를 수행하고 평균적으로 O(n log n)번의 비교를 수행합니다.

정렬되지 않은 데이터들에 대해서 속도와 효율성이 가장 좋다고 할 수 있는 정렬 방식입니다.

퀵 정렬의 알고리즘

---

1. 리스트 가운데에서 하나의 원소를 선택합니다. 이 원소를 피벗 이라고 칭합니다.

2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눕니다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 합니다. 분할은 마친 뒤에 피벗은 더이상 움직이지 않습니다.

3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복합니다. 재귀는 리스트의 크기가 0 혹은 1이 될 때까지 반복합니다.

위 설명을 간단하게 풀어보겠습니다.

- 퀵 정렬은 임의의 피벗값을 기준으로 좌측에는 피벗보다 작은 값, 우측에는 피벗보다 큰 값을 두고자 합니다.

- 피봇을 기준으로 좌 우로 이분화 된 리스트를 재귀적으로 반복했을 때 결국 정렬이 완성 된다는 방법 론 입니다.

퀵 정렬의 예제

---

임의의 값 피벗(4)을 선택합니다.

리스트의 왼쪽 끝은 i, 오른쪽 끝은 j 라고 가정합니다.

5 - 3 - 7 - 6 - 2 - 1 - 4 
                        p 

리스트 왼쪽에 있는 i 위치의 값(5)이 피벗보다 크고, 오른쪽에 있는 j 위치의 값(1) 이 피벗 값보다 작으므로 둘을 교환합니다.

5 - 3 - 7 - 6 - 2 - 1 - 4 
i                   j   p 
1 - 3 - 7 - 6 - 2 - 5 - 4 
i                   j   p 

작업이 끝났으면 i 위치를 오른쪽으로, j 위치를 왼쪽으로 전환합니다.

i 위치의 값(3) 도 피벗보다 작고, j 위치의 값(2) 도 피벗보다 작으므로 교환하지 않습니다.

1 - 3 - 7 - 6 - 2 - 5 - 4 
    i           j       p 

i 위치를 피벗 값보다 큰 값이 나올 때까지 우측으로 변경하며 j 와 비교해 만족하는 경우 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

퀵 정렬의 소스

---

#include <stdio.h>

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);
}

int main()
{
  int i;
  int list[10] = {5, 3, 8, 4, 9, 1, 6, 2, 7};

  quickSort(list, 0, 9);

  for(i=0; i<10; i++){
    printf("%d  ", list[i]);
  }
  return 0;
}

     위키에 첨부된 소스에서 main 함수를 넣어 완성시킨 코드입니다.

퀵 정렬의 정리

---

어떤 피벗을 선택할 것인가?

정렬된 배열에서는 퀵 정렬의 속도가 현저히 느려지게 되는데, 이러한 이유는 주로 피벗을 가장 오른쪽을 택하기 때문에 결과적으로 가장 큰 값이나 가장 작은 값이 되기 때문입니다.

피벗 값을 선택하는 대안으로는 난수로 선택하는 것인데, 이 부분은 속도 향상이 확률적입니다.

세 값의 중위 값을 구한 퀵 정렬의 속도 개선

배열의 가장 왼쪽, 오른쪽, 중간 값 3개를 사용합니다.

세 값을 정렬하여 가장 작은 값을 가장 왼쪽에 중간값을 중간에 가장 큰 값을 가장 오른쪽으로 이동시킵니다.

이 후 중간값을 가장 오른쪽의 앞과 변경합니다.

이렇게 되면, 배열의 첫번째 값은 마지막의 앞의 값보다 항상 작고, 마지막 값은 마지막 앞의 값보다 항상 크기 때문에 분할 구간이 좁혀지게 됩니다.

위처럼 범위를 2개 줄이게 되면 재귀의 깊이(반복횟수)도 줄일 수 있으므로 피벗선택이 효율적으로 이루어진다고  볼 수 있습니다.