[자료구조] 정렬의 속도 비교( 퀵 정렬, 삽입정렬, 병합 정렬)

다양한 정렬의 속도 비교

자료구조 중 삽입정렬, 병합정렬, 퀵 정렬을 비교하는 프로그램입니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//크기를 입력하면 1~크기로 채워서 배열을 생성
int* arrgen(int size) {
	int* arr = (int*)malloc(sizeof(int) * size);
	for (int i = 0; i < size; i++)
	{
		arr[i] = i+1;
	}
	return arr;
}

//임의의 두 원소를 교환하는 것을 epoch만큼 반복하는 함수
void shuffle(int arr[], int epoch,int size){
	srand((unsigned)time(NULL));
	for (int i = 0; i < epoch; i++) {
		long a,b,temp;
		//RANDOM_MAX를 넘기 위해서 비트연산
		a = (((long)rand() << 15) | rand()) % size;
		b = (((long)rand() << 15) | rand()) % size;
		temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

}

//삽입 정렬
void insertion_sort(int list[], int n)
{
	int i, j, key;
	for (i = 1; i < n; i++) {
		key = list[i];
		for (j = i - 1; j >= 0 && list[j] > key; j--)
			list[j + 1] = list[j];
		list[j + 1] = key;
	
	}
}

//병합정렬
void merge(int arr[], int left, int mid, int right)
{
	int f = left;
	int r = mid + 1;
	int i;

	int* sorted = (int*)malloc(sizeof(int) * (right + 1));
	int s = left;

	while (f <= mid && r <= right)
	{
		if (arr[f] <= arr[r])
			sorted[s] = arr[f++];
		else
			sorted[s] = arr[r++];

		s++;
	}

	if (f > mid)
	{
		for (i = r; i <= right; i++, s++)
			sorted[s] = arr[i];
	}
	else
	{
		for (i = f; i <= mid; i++, s++)
			sorted[s] = arr[i];
	}

	for (i = left; i <= right; i++)
		arr[i] = sorted[i];

	free(sorted);
}
void merge_sort(int arr[], int left, int right)
{
	int mid;

	if (left < right)
	{
		mid = (left + right) / 2;
		merge_sort(arr, left, mid);
		merge_sort(arr, mid + 1, right);
		merge(arr, left, mid, right);
	}
}

//퀵 정렬
void swap(int arr[], int idx1, int idx2)
{
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}


int partition(int arr[], int left, int right)
{
	int pivot = arr[left];    
	int low = left + 1;
	int high = right;

	while (low <= high)   
	{
		while (pivot > arr[low])
			low++;

		while (pivot < arr[high])
			high--;

		if (low <= high)    
			swap(arr, low, high);    
	}

	swap(arr, left, high);   
	return high;   
}

void quick_sort(int arr[], int left, int right)
{
	if (left <= right)
	{
		int pivot = partition(arr, left, right);   
		quick_sort(arr, left, pivot - 1);   
		quick_sort(arr, pivot + 1, right);   
	}
}
void printarr(int arr[], int size) {
	printf("current array :\n");
	for (int i = 0; i < size; i++) {
		printf("%d\n", arr[i]);
		if (i >= 29)
			break;

	}
}
int* copyarr(int arr[],int size) {
	int* tmparr = (int*)malloc(sizeof(int) * size);
	for (int i = 0; i < size; i++) {
		tmparr[i] = arr[i];
	}
	return tmparr;
}

//메인 함수
int main() {
	
	while (1) {
		int size, epoch;
		printf("Number of Data (0 exit) : ");
		scanf_s("%d", &size);
		while (size > 100000 ) {
			printf("Please input INTEGER NUMBER in 1 ~ 100000\nEntering 0 or a negative number will terminate this program.\n\n");
			printf("Number of Data (0 exit) : ");
			scanf_s("%d", &size);
			if (size <= 0) break;
		}
		if (size <= 0) break;

		int* arr = arrgen(size);



		//printarr(arr,size);

		printf("Number of time to shuffle: ");
		scanf_s("%d", &epoch);
		shuffle(arr, epoch, size);

		//printarr(arr, size);

	/*	배열 복사를 이용해 동일한 배열로 평가하고 싶은 경우
		int* copy1 = copyarr(arr, size);
		int* copy2 = copyarr(arr, size);
		int* copy3 = copyarr(arr, size);*/

		clock_t s, e;
		double t;

		s = clock();
		insertion_sort(arr, size);
		e = clock();//시간 측정
		t = (double)(e - s) / CLOCKS_PER_SEC;

		//printarr(arr, size);
		printf("  Insertion sort: %.3f sec\n", t);



		shuffle(arr, epoch, size);

		//printarr(arr, size);

		s = clock();
		merge_sort(arr, 0, size - 1);
		e = clock();//시간 측정
		t = (double)(e - s) / CLOCKS_PER_SEC;

		//printarr(arr, size);
		printf("  Merge sort: %.3f sec\n", t);
		shuffle(arr, epoch, size);

		//printarr(arr, size);

		s = clock();
		quick_sort(arr, 0, size - 1);
		e = clock();//시간 측정
		t = (double)(e - s) / CLOCKS_PER_SEC;


		//printarr(arr, size);
		printf("  Quick sort: %.3f sec\n", t);

		printf("\n");

	}
	return 0;
}

 

출력 예시