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

스택을 이용한 순환제거

소스 코드

#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
const int N = 10000000;
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;
}

 

class Stack {
  public:
    Stack(int max=100) { stack = new int[max]; p = 0; }
    ~Stack() { delete stack; }
    inline void push(int v) { stack[p++] = v; }
    inline int pop() { return stack[--p]; }
    inline int empty() { return !p; }
  private:
    int *stack;
    int p;
};
   

int partition(int a[], int l, int r)
{
  int i, j, pivot;
  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);
  return i;
}

void QuickSort(int a[], int l, int r)
{
  int i;
  Stack st(50);
  while (true) {
    while (r > l) {
      i = partition(a, l, r);
      if (i-l > r-i) {
        st.push(l); st.push(i-1); l = i+1;
      }
      else {
        st.push(i+1); st.push(r); r = i-1;
      }
    }
    if (st.empty()) break;
    r = st.pop(); l = st.pop();
  }
}

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