[c++] 알고리즘 - 퀵 정렬 향상방법3

중간 값 분할

- 분할 원소를 선택할 때 왼쪽, 가운데, 오른쪽 원소 중 값이 중간인 원소를 선택

- 왼쪽, 가운데, 오른쪽 원소를 정렬한 후 가장 작은 값을 a[l], 가장 큰 값을 a[r], 중간 값을 a[r-1]에 넣고, a[l+1], …, a[r-2]에 대해 분할 알고리즘을 수행

 

 

 

특징

- 최악의 경우가 발생하는 확률을 낮추어 줌

- 경계 키(sentinel key)를 사용할 필요가 없음

- 전체 수행 시간을 약 5% 감소시킴

 

 

 

소스 코드

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

using namespace std;
const int N = 10000000;
const int TRUE = 1;
const int FALSE = 0;
int a[N+1];

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 QuickSort(int a[], int l, int r)
{
  int i, j, m, pivot;
  if (r - l > 1) {
    m = (l + r) / 2;
    if (a[l] > a[m]) swap(a, l, m);
    if (a[l] > a[r]) swap(a, l, r);
    if (a[m] > a[r]) swap(a, m, r);
    swap(a, m, r-1);
    pivot = a[r-1]; i = l; j = r-1; 
    while (true) {
      while (a[++i] < pivot);
      while (a[--j] > pivot);
      if (i >= j) break;
      swap(a, i, j);
    }
    swap(a, i, r-1);
    QuickSort(a, l, i-1);
    QuickSort(a, i+1, r);
  }
  else if (a[l] > a[r]) swap(a, l, r);
}

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