1418: [정렬] 퀵 정렬

정보과학 교과서 156p
----

퀵 정렬(quick sort)은 주어진 데이터들을 
특정 기준값(pivot)의 왼쪽에 그 기준값보다 작은 값들이 배치되도록,
특정 기준값의 오른쪽에 그 기준값보다 큰 값들이 배치되도록 데이터들을 이동시키는 과정을 반복하는 정렬 방법이다.

일단, 주어진 기준값을 중심으로 2개의 부분으로 정리가 되면, 각각의 부분에 대해서도 똑같은 방법을 적용해 정렬해 나가는 방법이다.

퀵 정렬은 기준값을 중심으로 2개의 그룹으로 이동시키는 과정을 통해서 매우 빠르게(quick) 정렬된다.

기준값을 잡는 방법에 따라서 효율이 조금씩 달라지기도 한다.

n개의 정수 데이터를 입력받아 오름차순으로 정렬하여 출력하는 프로그램을 작성해보자.
단, 정렬 함수 sort() 를 사용할 수 없다.

#include <stdio.h>
int n, d[100010];

void quicksort(int l, int r)
{
  if(l>=r) return;

  int pivot = d[l];                             //첫 번째 값을 기준값(pivot)으로 설정
  int p = l+1;
  int q = r;

  while(true)
  {
    while(d[p]<=pivot && p<r) p++;  //왼쪽에서 오른쪽으로 가면서 기준값보다 큰 값을 찾고
    while(d[q]>pivot && q>l) q--;       //오른쪽에서 왼쪽으로 가면서 기준값보다 작거나 같은 값을 찾고

    if(p<q)                                        //큰 값이 왼쪽에 있고, 작은 값이 오른쪽에 있으면 서로 자리를 바꿈
    {
      int t = d[p];
      d[p] = d[q];
      d[q] = t;
    }
    else                                            //큰 값이 오른쪽에 있으면, 작은 값과 기준 값의 자리를 서로 바꿈
    {
      int t = d[l];
      d[l] = d[q];
      d[q] = t;
      break;                                      //이렇게 하면, 기준값을 중심으로 작은 값들은 모두 왼쪽, 큰 값들을 모두 오른쪽에 위치하게 됨.
    }
  }

  //분할 정복
  quicksort(l, q-1);   // 기준값의 왼쪽에 있는 작은 값들에 대해서 같은 방법으로 정렬
  quicksort(q+1, r);  // 기준값의 오른쪽에 있는 큰 값들에 대해서 같은 방법으로 정렬
}

int main()
{
  scanf("%d", &n);

  for(int i=1; i<=n; i++)
    scanf("%d", &d[i]);

  quicksort(1, n);         //구간 [1, n]에 대해서 퀵정렬 시작

  for(int i=1; i<=n; i++)
    printf("%d\n", d[i]);
}

첫 번째 줄에 데이터의 개수(n)가 입력된다.
두 번째 줄에는 n개의 데이터(k)가 스페이스를 사이에 두고 한 줄로 입력된다.
[1 <= n <= 100000]
[0 <= k <= 2147483647]

오름 차순으로 정렬한 결과를 스페이스를 사이에 두고 한 줄로 출력한다.

5
9 8 3 4 7

3 4 7 8 9