[알고리즘] Assignment 3 - 정렬 알고리즘 (bubble sort, insertion sort, merge sort, quick sort, radix sort, bucket sort)

1. Code

#include <stdio.h>
#include <time.h>
#define SIZE 1000
#define DIGIT 4

int origin[SIZE], result[SIZE], result_2[SIZE];

void bubble_sort() 
{
	int i, j, temp;
	for (i = SIZE - 1; i > 0; i--) {
		for (j = 0; j < i; j++) {
			if (origin[j] > origin[j + 1]) {
				temp = origin[j];
				origin[j] = origin[j + 1];
				origin[j + 1] = temp;
			}
		}
	}
}

void insertion_sort() 
{
	int i, j, temp;
	for (i = 1; i < SIZE; i++) {
		temp = origin[i];
		for (j = i - 1; origin[j] > temp  && j >= 0; j--) {    // 확인
			origin[j + 1] = origin[j];
		}
		origin[j + 1] = temp;
	}
}

void merge(int left, int middle, int right)
{
	int i = left;
	int j = middle + 1;
	int current = left;
	int k;

	while (i <= middle && j <= right) {
		if (origin[i] <= origin[j]) {
			result_2[current++] = origin[i++];
		} else {
			result_2[current++] = origin[j++];
		}
	}

	if (i > middle) {
		for (k = j; k <= right; k++) {
			result_2[current++] = origin[k];
		}
	} else {
		for (k = i; k <= middle; k++) {
			result_2[current++] = origin[k];
		}
	}

	// result[] 배열 사용 가능 시 아래 for문 제거
	for (k = left; k <= right; k++) {
		origin[k] = result_2[k];
	}
}

void merge_sort(int left, int right)     // error
{
	int middle;
	if (left < right)
	{
		middle = (left + right) / 2;
		merge_sort(left, middle);
		merge_sort(middle + 1, right);
		merge(left, middle, right);
	}
}

void quick_sort(int left, int right)     // error
{
	int pivot = origin[left];
	int i = left + 1, j = right, temp;

	if (left <= right) {
		while (i <= j) {
			while (i <= right && pivot >= origin[i]) i++;
			while (j >= left + 1 && pivot <= origin[j]) j--;
			if (i <= j) {
				temp = origin[i];
				origin[i] = origin[j];
				origin[j] = temp;
			}
		}

		temp = origin[left];
		origin[left] = origin[j];
		origin[j] = temp;

		quick_sort(left, j - 1);
		quick_sort(j + 1, right);
	}
}

void radix_sort() //queue
{
	int i, fctr;
	int max = origin[0];

	for (i = 1; i < SIZE; i++) {
		if (origin[i] > max) max = origin[i];
	}

	for (fctr = 1; max / fctr > 0; fctr *= 10) {
		int temp[10] = { 0 };

		for (i = 0; i < SIZE; i++) {
			temp[(origin[i] / fctr) % 10]++;
		}

		for (i = 1; i < 10; i++) {
			temp[i] += temp[i - 1];
		}

		for (i = SIZE - 1; i >= 0; i--) {
			result[--temp[(origin[i] / fctr) % 10]] = origin[i];
		}

		// result[] 배열 사용 가능 시 아래 for문 제거
		for (i = 0; i < SIZE; i++) {
			origin[i] = result[i];
		}
	}
}

void bucket_sort() 
{
	int bucket[10][SIZE];
	int count[10] = { 0 };
	int tens = 1, val, cnt;
	int i, j, k;

	for (i = 1; i < DIGIT + 1; i++) {
		for (j = 0; j < i - 1; j++) {
			tens *= 10;
		}
		for (j = 0; j < SIZE; j++) {
			val = int(origin[j] / tens) % 10;
			bucket[val][count[val]] = origin[j];
			count[val]++;
		}
		cnt = 0;
		for (j = 0; j < 10; j++) {
			for (k = 0; k < count[j]; k++) {
				origin[cnt] = bucket[j][k];
				cnt++;
			}
		}
		for (j = 0; j < 10; j++) {
			count[j] = 0;
		}
	}
}

void set_origin(int temp[]) {
	for (int i = 0; i < SIZE; i++) {
		origin[i] = temp[i];
	}
}

int main()
{
	int temp[SIZE], i;
	clock_t start, end, exe_time;

	for (i = 0; i < SIZE; i++) {
		temp[i] = SIZE - i;
	}
	
	printf("original array : ");
	for (i = 0; i < SIZE; i++) {
		printf("%5d ", temp[i]);
	}
	printf("\n\n");


	set_origin(temp);
	start = clock();
	bubble_sort();
	end = clock();
	printf("%f %f \n", (float)start, (float)end);
	exe_time = end - start;
	printf("bubble-sorted array : ");
	for (i = 0; i < SIZE; i++) {
		printf("%5d ", origin[i]);
	}
	printf("\n");
	printf("Bubble Sort Execution Time : %f seconds\n\n", (float)exe_time / CLOCKS_PER_SEC);

	set_origin(temp);
	start = clock();
	insertion_sort();
	end = clock();
	exe_time = end - start;
	printf("%f %f \n", (float)start, (float)end);
	printf("insertion-sorted array : ");
	for (i = 0; i < SIZE; i++) {
		printf("%5d ", origin[i]);
	}
	printf("\n");
	printf("Insertion Sort Execution Time : %f seconds\n\n", (float)exe_time / CLOCKS_PER_SEC);

	set_origin(temp);
	start = clock();
	merge_sort(0, SIZE-1);
	end = clock();
	exe_time = end - start;
	printf("%f %f \n", (float)start, (float)end);
	printf("merge-sorted array : ");
	for (i = 0; i < SIZE; i++) {
		printf("%5d ", origin[i]);
	}
	printf("\n");
	printf("Merge Sort Execution Time : %f seconds\n\n", (float)exe_time / CLOCKS_PER_SEC);

	set_origin(temp);
	start = clock();
	quick_sort(0, SIZE-1);
	end = clock();
	exe_time = end - start;
	printf("%f %f \n", (float)start, (float)end);
	printf("quick-sorted array : ");
	for (i = 0; i < SIZE; i++) {
		printf("%5d ", origin[i]);
	}
	printf("\n");
	printf("Quick Sort Execution Time : %f seconds\n\n", (float)exe_time / CLOCKS_PER_SEC);

	set_origin(temp);
	start = clock();
	radix_sort();
	end = clock();
	exe_time = end - start;
	printf("%f %f \n", (float)start, (float)end);
	printf("radix-sorted array : ");
	for (i = 0; i < SIZE; i++) {
		printf("%5d ", origin[i]);
	}
	printf("\n");
	printf("Radix Sort Execution Time : %f seconds\n\n", (float)exe_time / CLOCKS_PER_SEC);

	set_origin(temp);
	start = clock();
	bucket_sort();
	end = clock();
	exe_time = end - start;
	printf("%f %f \n", (float)start, (float)end);
	printf("bucket-sorted array : ");
	for (i = 0; i < SIZE; i++) {
		printf("%5d ", origin[i]);
	}
	printf("\n");
	printf("Bucket Sort Execution Time : %f seconds\n\n", (float)exe_time / CLOCKS_PER_SEC);
}

 

 

2. Display

 

1) Set the inputs assuming the worst-case.

for ( i = 0 ; i < SIZE ; i ++ ) {
	temp [ i ] = SIZE - i ;
}

 

2) size 10

 

3) size 100

 

4) size 1000

 

 

3. Result table

	Bubble	Insertion	Merge	Quick	Radix	Bucket
10	0.000	0.000	0.000	0.000	0.000	0.000
100	0.000	0.000	0.000	0.000	0.000	0.000
1000	0.001	0.001	0.000	0.001	0.000	0.000
(3000)	0.009	0.005	0.000	0.004	0.000	0.000

(sec)

 

* I think my computer is way-too fast to make this result meaningful, so I increased the input size to 3,000.