각종 정렬 시간 비교

예전에 알고리즘 수업시간에 과제로 짜놨던건데 유용하게 쓰일것 같아서 올려놓는다. 언어는 c++이다.

#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
const int N = 500000;

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

void QuickSort(int a[], int l, int r) //퀵정렬 원래알고리즘
{
	int i,j,v;
	if(r > l)
	{
		v = a[r]; i=l-1; j=r;
		for(;;)
		{
			while (a[++i] < v);
			while (a[--j] > v);
			if (i >=j) break;
			swap(a,i,j);
		}
		swap(a,i,r);
		QuickSort(a,l,i-1);
		QuickSort(a,i+1,r);
	}
}

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,v;
	v =a[r]; i = l-1; j=r;
	for(;;)
	{
		while (a[++i] < v);
		while (a[--j] > v);
		if(i >= j) break;
		swap(a,i,j);
	}
	swap(a,i,r);
	return i;
}
void QuickSort2(int a[], int l, int r)
{
	int i;
	Stack sf(50);
	for(;;)
	{
		while(r > l)
		{
			i = partition(a,l,r);
			if(i-l > r-i)
			{
				sf.push(l); sf.push(i-1); l = i+1;
			}
			else
			{
				sf.push(i+1); sf.push(r); r = i-1;
			}
		}
		if(sf.empty()) break;
		r = sf.pop(); l = sf.pop();
	}
}

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

void QuickSort4(int a[], int l, int r)//중간 값 분할을 사용한 퀵 정렬 프로그램
{
	int i,j,m,v;
	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);
		v = a[r-1]; i=l; j = r-1;
		for(;;)
		{
			while(a[++i] < v);
			while(a[--j] > v);
			if(i >=j) break;
			swap(a,i,j);
		}
		swap(a,i,r-1);
		QuickSort4(a,l,i-1);
		QuickSort4(a,i+1,r);
	}
	else if (a[l] > a[r]) swap(a,l,r);
}

int b[N+1];
void MergeSort(int a[], int l, int r) //합병 정렬
{
	int i,j,k,m;
	if(r > l)
	{
		m = (r+l) / 2;
		MergeSort(a,l,m);
		MergeSort(a,m+1,r);
		for(i=m+1;i>l;i--) b[i-1] = a[i-1];
		for(j=m;j<r;j++) b[r+m-j] = a[j+1];
		for(k=l;k<=r;k++)
			a[k] = (b[i] < b[j]) ? b[i++] : b[j--];
	}
}

void merge(int a[], int l, int m, int r) //자연 합병 정렬
{
	int i, j, k;
	for (i = m+1; i > l; i--) b[i-1] = a[i-1];
	for (j = m; j < r; j++) b[r+m-j] = a[j+1];
	for (k = l; k <= r; k++) a[k] = (b[i] < b[j]) ? b[i++] : b[j--];
}
int makeRun(int a[], int run[])
{
	int i = 1, j = 1;
	for (i = 1; i <= N; i++) {
		if (a[i] > a[i+1]) {
			run[j++] = i;
		}
	}
	//printList(run, j-1);
	return j-1;
}
int moveRun(int run[], int cnt)
{
	int i, j = 1;
	for (i = 2; i <= cnt; i += 2) run[j++] = run[i];
	if ((cnt % 2) != 0) run[j] = run[i-1]; // cnt가 홀수일 때 마지막 run 처리
	else j--;
	//printList(run, j);
	return j;
}
void NaturalMergeSort(int a[], int n)
{
	int i, num;
	int cnt; // number of runs
	int run[N+1];
	run[0] = 0; 
	cnt = makeRun(a, run);
	while (cnt > 1) { 
		if ((cnt % 2) != 0) num = cnt-1; // cnt가 홀수일 때는 cnt 값을 하나 감소
		else num =  cnt;
		for (i = 1; i <= num; i += 2) 
			merge(a, run[i-1]+1, run[i], run[i+1]);	  
		cnt = moveRun(run, cnt); 
	}
}

void heapify(int a[], int h, int m) //히프 정렬. bottom-up
{
	int j,v;
	v = a[h];
	for(j=2*h; j<=m; j*=2)
	{
		if(j < m && a[j] < a[j+1]) j++;
		if(v >= a[j]) break;
		else a[j/2] = a[j];
	}
	a[j/2] = v;
}
void HeapSort(int a[], int n)
{
	int i;
	for(i=n/2;i>=1;i--)
		heapify(a,i,n);
	for(i=n-1;i>=1;i--)
	{
		swap(a,1,i+1);
		heapify(a,1,i);
	}
}

void heapify2(int a[], int h, int m) //히프정렬. top-down
{
   int v;
   v = h;
   for(int j=h/2; j>=1; j/=2){
      if(a[v] >= a[j]){
         swap(a,v,j);
         v = j;
      }
      else 
		  break;
   }
}
void HeapSort2(int a[], int n)
{
   for(int i=1;i<=n;i++){
      heapify2(a,i,n);
   }
   for(int i=n-1;i>=1;i--){
      swap(a,1,i+1);
      heapify(a,1,i);
   }
}

int main (void)
{
	int i,a[N+1];
	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;
	CheckSort(a,N);

	for(i=1;i<=N;i++) a[i] = rand();
	start_time = clock();
	QuickSort2(a,1,N);
	cout<<"순환을 제거한 퀵 정렬의 실행 시간 (N = "<<N<<") "<<clock()-start_time<<endl;
	CheckSort(a,N);

	for(i=1;i<=N;i++) a[i] = rand();
	start_time = clock();
	QuickSort3(a,1,N);
	cout<<"작은 부분파일을 고려한 퀵 정렬의 실행 시간 (N = "<<N<<") "<<clock()-start_time<<endl;
	CheckSort(a,N);

	for(i=1;i<=N;i++) a[i] = rand();
	start_time = clock();
	QuickSort4(a,1,N);
	cout<<"중간 값 분할을 사용한 퀵 정렬의 실행 시간 (N = "<<N<<") "<<clock()-start_time<<endl;
	CheckSort(a,N);

	for(i=1;i<=N;i++) a[i] = rand();
	start_time = clock();
	MergeSort(a,1,N);
	cout<<"합병 정렬의 실행 시간 (N = "<<N<<") "<<clock()-start_time<<endl;
	CheckSort(a,N);

	for(i=1;i<=N;i++) a[i] = rand();
	start_time = clock();
	NaturalMergeSort(a,N);
	cout<<"자연합병 정렬의 실행 시간 (N = "<<N<<") "<<clock()-start_time<<endl;
	CheckSort(a,N);

	for(i=1;i<=N;i++) a[i] = rand();
	start_time = clock();
	HeapSort(a,N);
	cout<<"bottom-up히프 정렬의 실행 시간 (N = "<<N<<") "<<clock()-start_time<<endl;
	CheckSort(a,N);

	for(i=1;i<=N;i++) a[i] = rand();
	start_time = clock();
	HeapSort2(a,N);
	cout<<"top-down히프 정렬의 실행 시간 (N = "<<N<<") "<<clock()-start_time<<endl;
	CheckSort(a,N);

	return 0;
}