[c++] 알고리즘 - 퀵 정렬

퀵 정렬 (Quick Sort)

- 1960년 C.A.R. Hoare에 의해 개발

- 분할 정복(divide and conquer) 기법을 사용한 정렬 방법의 하나

- 현재 가장 광범위하게 쓰이는 정렬 알고리즘

- 퀵 정렬의 성능을 개선하려는 시도가 있었지만 큰 성과를 거두지 못함

 

 

 

 

특징

- 평균적으로 아주 좋은 성능을 가짐

- 약간의 작은 스택만 있으면 별도의 메모리를 요구하지 않음

- 불안정적인 제자리 알고리즘

- N 개의 원소를 정렬하는데 평균적으로 N logN 의 연산속도를 가짐

 

  

 

 

 

 기본 알고리즘

1. 배열 a[l : r] a[r]을 피봇(pivot)으로 선정

2. 피봇을 기준으로 a[]의 원소들을 두 개의 파티션(partition)으로 분할

- 분할 후 피봇은 a[i]에 들어가게 되는데, 이곳은 정렬 후 피봇이 들어가는 정확한 위치가 됨

- 왼쪽 파티션에 있는 원소 a[l], …, a[i-1] 중 피봇보다 큰 원소는 없음

- 오른쪽 파티션에 있는 원소 a[i+1], …, a[r] 중 피봇보다 작은 원소는 없음

 

 

 

 

 

수행과정

 

 

 

 

 

 

성능 특성

최선의 경우

- CN = 2CN/2 + N

- CN » N logN 

평균

- CN » 2N lnN

평균 비교 횟수는 최선의 경우에 비해 약 38% 정도많아지므로 큰 차이가 나지 않는다고 할 수 있음

- 2N lnN  » 1.38 N logN

 

 

 

 

 

 

소스 코드

#include <iostream>
#include <time.h>
#include <stdlib.h>

using namespace std;

const int N = 4000;
int a[N+1];
const int TRUE = 1;
const int FALSE = 0;

inline void swap(int a[], int i, int j)
{
  int t = a[i]; a[i] = a[j]; a[j] = t;
}

void CheckTime(int a[], int n)
{
  int i, Sorted;
  Sorted = TRUE;
  for (i = 1; i < n; i++) {
    if (a[i] > a[i+1]) Sorted = FALSE;
    if (!Sorted) break;
  }
  if (Sorted) cout << "정렬 완료." << endl;
  else cout << "정렬 오류 발생." << endl;
}
void printList(int a[], int n)
{
 int i;
 for (i = 1; i < n; i++)
  cout << a[i] << ", ";
 cout << a[i] << endl;
}

void QuickSort(int a[], int l, int r)
{
  int i, j, pivot;
  if (r > l) {
    pivot = a[r]; i = l-1; j = r;
    while(true) {
      while (a[++i] < pivot);
      while (a[--j] > pivot);
      if (i >= j) break;
      swap(a, i, j);
    }
    swap(a, i, r);
    QuickSort(a, l, i-1);
    QuickSort(a, i+1, r);
  }
}

int main()
{
  //int i;
  //double start_time;

  a[0] = -1;   // 감시 키
  //srand(time(NULL));
  //for (i = 1; i <= N; i++) a[i] = rand();

 

  //start_time = clock();
  QuickSort(a, 1, N);
  //cout << "퀵 정렬의 실행 시간 (N = " << N << ") : " <<
           clock() - start_time << endl;
  //CheckTime(a, N);
}

 

 

 

퀵정렬의 성능 향상 방법

- 스택을 사용하여 순환을 제거

- 작은 부분화일의 경우 삽입정렬 사용

- 중간값 분할 (median - of - Three Partitioning)