[알고리즘] 퀵 정렬(Quick Sort)이란? | c언어 퀵 정렬 구현

퀵 정렬(Quick Sort)

퀵 정렬은 합병정렬과 비슷하게 분할정복(Divide and Conquer) 알고리즘이다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 다음과 같은 과정을 거친다.

 

1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot(피벗) 이라고 한다.
2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다.
3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
  3-1) 분할된 왼쪽 리스트와 오른쪽 리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다.
  3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 할 때까지 반복한다. 

 

그림을 예시로 들어 이해해보자.

위와 같은 배열을 오름차순으로 퀵 정렬 한다고 하자. 가장 먼저 pivot을 설정해야 하는데, pivot을 설정하는 것에는 여러가지 방법이 있다. 가장 앞의 원소, 중간 원소, 혹은 가장 뒤의 원소를 택하는 등의 방법이 있는데 여기서는 중간 원소를 pivot값으로 설정하는 것을 택하겠다.

 

• 중간 값을 pivot으로 설정했다면 가장 왼쪽의 값을 left, 오른쪽의 값을 right로 잡는다. (여기서 L은 배열의 가장 왼쪽, R은 가장 오른쪽의 위치를 나타낸다) 
• left는 오른쪽으로, right는 왼쪽으로 이동하게 되는데 이 때
• left는 pivot보다 큰 수를 만나거나 pivot을 만나면 멈추고, 
• right는 pivot보다 작은 수를 만나거나 pivot을 만나면 멈춘다.
• 따라서 5가 3보다 크므로 left는 5에서 멈추고, 2가 3보다 작으므로 right는 2에서 멈춘다.

 

• left와 right가 멈췄을 때, left가 right보다 왼쪽에 있다면 left와 right 값을 교환해준다.
• 이후 left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동해준다.
• 위 과정을 left가 right 보다 오른쪽으로 올 때까지 반복한다.

 

• 6이 3보다 크므로 6에서 left가 멈춘다.
• right는 pivot을 만나서 멈춘다. 
• 이 때 left가 right보다 왼쪽에 있으므로 left와 right 값을 교환한다.
• left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동한다.
• left 가 right 보다 오른쪽에 있으므로 종료한다.

 

• right가 L보다 크다면 L부터 right까지 다시 위 과정을 재귀적으로 반복한다.
• left가 R보다 작다면 left부터 R까지 다시 위 과정을 재귀적으로 반복한다.

• 왼쪽 부분 배열 정렬 과정
  • left는 2에서 멈춘다.
  • right는 pivot에서 멈춘다.
  • left가 right보다 왼쪽에 있으므로 둘을 교환한다.
  • left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동한다.
  • left가 right보다 오른쪽에 있으므로 종료한다.
  • 이때 right가 L보다 크지 않으므로 왼쪽배열(L부터 right)은 다시 재귀적으로 정렬할 필요가 없다.
  • left는 R보다 작으므로 left부터 R까지 다시 재귀적으로 정렬을 수행한다. 
• 오른쪽 부분 배열 정렬 과정
  • left는 6에서 멈춘다.
  • right는 pivot에서 멈춘다.
  • left가 right보다 왼쪽에 있으므로 둘을 교환한다.
  • left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동한다.
  • left가 right보다 오른쪽에 있으므로 종료한다.
  • 이때 right가 L보다 크지 않으므로 왼쪽배열(L부터 right)은 다시 재귀적으로 정렬할 필요가 없다.
  • left는 R보다 작으므로 left부터 R까지 다시 재귀적으로 정렬을 수행한다.
• 이 후 과정도 동일하므로 생략하겠다.

위와 같은 과정을 거치면 배열이 위와 같이 오름차순으로 정렬된다.

 

퀵 정렬 특징

• 퀵정렬은 재귀적으로 정의되므로 재귀 호출에 따른 스택이 사용된다. 이때 스택의 깊이는 n개의 원소에 대해 logn에 비례하므로 공간복잡도는 O(nlogn)이다. 따라서 in-place 정렬이라고 하기 힘들지만, 실용적으로는 상대적으로 작은 메모리만을 사용하므로 흔히 in-place 정렬이라고 기술하기도 한다. 
• 퀵정렬은 최악의 경우 pivot이 배열 내에서 가장 작은 값 또는 가장 큰 값으로 설정된다면 원소 n개에 대해서 n번, (n-1)번, (n-2)번...1번 의 비교가 필요하므로 시간 복잡도가 O(n^2) 된다.
• 하지만 평균 시간 복잡도는 O(nlogn)으로 매우 빠르다. pivot 값이 적절히 설정된다면 그 속도가 매우 빠르다. 따라서 pivot값을 잘 설정하는 것이 중요하다.
• 퀵 정렬은 중복된 키값이 순서대로 바뀌지 않을 수 있어 (예를 들어 {7,7,1}을 오름차순으로 퀵정렬해보라) not-stable 하다.

 

소스코드

# include <stdio.h>
# define LEN 7
 
void quickSort(int arr[], int L, int R) {
      int left = L, right = R;
      int pivot = arr[(L + R) / 2];    // pivot 설정 (가운데) 
      int temp;
      do
      {
        while (arr[left] < pivot)    // left가 pivot보다 큰 값을 만나거나 pivot을 만날 때까지 
            left++;
        while (arr[right] > pivot)    // right가 pivot보다 작은 값을 만나거나 pivot을 만날 때까지 
            right--;
        if (left<= right)    // left가 right보다 왼쪽에 있다면 교환 
        {
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            /*left 오른쪽으로 한칸, right 왼쪽으로 한칸 이동*/
            left++;
            right--;
        }
      } while (left<= right);    // left가 right 보다 오른쪽에 있을 때까지 반복 
 
    /* recursion */
    if (L < right)
        quickSort(arr, L, right);    // 왼쪽 배열 재귀적으로 반복 
 
    if (left < R)
        quickSort(arr, left, R);    // 오른쪽 배열 재귀적으로 반복 
}
 
int main(){
  int i;
  int arr[LEN] = {5,1,6,3,4,2,7};
  printf("정렬 전 : ");
  for(i=0; i<LEN; i++){
    printf("%d ", arr[i]);
  }
  printf("\n");
    
  quickSort(arr, 0, LEN-1);
  
  printf("정렬 후 : ");
  for(i=0; i<LEN; i++){
    printf("%d ", arr[i]);
  }
  
  return 0; 
}

 

실행결과

---