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

작은 부분화일

부분화일의 크기가 일정 크기 이하로 작아지면 삽입 정렬 수행

“if (r > l)”

- “if (r - l <= M) InsertionSort(a, l, r)”

M : 5 ~ 25

많은 응용에서 약 20% 정도의 시간 절감 효과가 있음

 

 

 

 

소스 코드

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

using namespace std;

const int N = 10000000;
const int M = 20;
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 InsertionSort(int a[], int l, int r)
{
  int i, j, v;
  for (i = l+1; i <= r; i++) {
    v = a[i]; j = i;
    while (a[j-1] > v) {
      a[j] = a[j-1]; j--;
    }
    a[j] = v;
  }
}

void QuickSort(int a[], int l, int r)
{
  int i, j, pivot;
  if (r-l <= M) InsertionSort(a, l, r);
  else {
    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);
  }
}

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

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

  QuickSort(a, 1, N);
  //cout << "작은 서브화일을 고려한 퀵 정렬의 실행 시간 (N = " << N << ") : " <<
           clock() - start_time << endl;
  //CheckTimet(a, N);
}