Quick Sort(퀵 정렬) - 가장 효율적인 오름차순 정렬법

알고리즘 문제를 풀다가 배열의 원소들을
오름차순으로 정렬해야 할 필요가 생겼습니다.

원소들을 가장 작은 값부터 순서대로 나열하려면
어떻게 해야 할까요?

여러 방법들이 있지만
그중 시간 복잡도 및 공간 복잡도가 가장 낮은,
가장 효율적인 정렬법을 소개하고자 합니다.

바로 퀵 정렬(Quick Sort)입니다.

---

퀵 정렬 알고리즘

1. 배열의 가운데에 위치한 원소를
pivot 값으로 설정합니다.

* pivot: 중심점

2. 가장 왼쪽의 값을 left,
오른쪽의 값을 right로 잡습니다.

3. left는 오른쪽으로,
right는 왼쪽으로 이동하게 됩니다.
이때 left는 이동하면서
pivot보다 큰 수를 만나거나
pivot을 만나면 멈추고,
right는 이동하다가
pivot보다 작은 수를 만나거나
pivot을 만나면 멈춥니다.

4. left와 right가 멈췄을 때,
left가 right보다 왼쪽에 있다면
left와 right 값을 교환해줍니다.

5. 이후 left를 오른쪽으로 한 칸,
right를 왼쪽으로 한 칸 이동해줍니다.

위 과정을 left가 right 보다
오른쪽으로 올 때까지 반복합니다.

---

특징

공간 복잡도: O(nlogn)

평균 시간 복잡도: O(nlogn)

퀵 정렬을 사용했을 때 최악의 경우는
pivot이 배열 내에서 가장 작은 값 또는
가장 큰 값으로 설정됐을 때입니다.
원소 n개에 대해서
n번, (n-1)번, (n-2)번 ... 1번의 비교가 필요하므로
시간 복잡도가 O(n^2)가 됩니다.

하지만 pivot 값이 적절히 설정된다면
평균 시간 복잡도는 O(nlogn)으로 매우 빠릅니다.

따라서 pivot 값을 잘 설정하는 것이 중요합니다.

퀵 정렬은 중복된 원소 값이
순서대로 바뀌지 않을 수 있어
안정적이지 않습니다.
(그 예로 [ 7, 7, 1 ]를 통해 확인해 볼 수 있습니다.)

---

C언어 코드

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

 

출처: https://code-lab1.tistory.com/23 [코드 연구소:티스토리]