Time Complexity Comparison Among Sorting Algorithms

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "bobbleSort.h"
#include "selectionSort.h"
#include "insertionSort.h"
#include "mergeSort.h"
#include "quickSort.h"
#include "heapSort.h"

#define RANDOM(__min__, __max__) \
	((int)(((double)((rand()<<15) | rand())) / ((RAND_MAX<<15 | RAND_MAX) + 1) \
		* (((__max__) + 1) - (__min__))) + (__min__))

int* create_test_array(int N) {
	int* data = (int*)malloc(sizeof(int) * N);

	if (data == NULL)
	{
		printf("Memory Allocation Error");
		exit(1);
	}

	for (int i = 0; i < N; i++) {
		data[i] = RANDOM(1,N);
	}

	return data;
}

int static compare(const void* first, const void* second)
{
	if (*(int*)first > *(int*)second)
		return 1;
	else if (*(int*)first < *(int*)second)
		return -1;
	else
		return 0;
}

void test(int N, int mode) {

	clock_t time_start = clock();

	for (int i = 0; i < 10; i++) {
		int* data = create_test_array(N);
		if (mode == 1)
			bubbleSort(data, N);
		if (mode == 2)
			selectionSort(data, N);
		if (mode == 3)
			insertionSort(data, N);
		if (mode == 4)
			mergeSort(data, 0, N - 1);
		if (mode == 5)
			quickSort(data, 0, N - 1, 1);
		if (mode == 6)
			quickSort(data, 0, N - 1, 2);
		if (mode == 7)
			quickSort(data, 0, N - 1, 3);
		if (mode == 8)
			heapSort(data, 0, N - 1);
		if (mode == 9)
			qsort(data, N, sizeof(int), compare);
		free(data);
	}

	clock_t time_end = clock();

	printf("%.3lf\t", (double)(time_end - time_start)/1000);
}

• 10 * (1000, 10000, 100000)번 실행

time.h의 rand()함수는 0 ~ 32767 (RAND_MAX)의 값만 리턴한다.

RAND_MAX 이상의 큰 수 범위의 랜덤(random) 값 구하기