학창 시절에 만든 C언어 정렬비교

SortData.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>
#pragma warning(disable:4996)

// 선택 정렬
void SelectionSort(int list[], int n)
{
	int i, j, least, temp;
	temp = 0;
	for (i = 0; i<n - 1; i++)
	{
		least = i;
		for (j = i + 1; j<n; j++)	// 최솟값 탐색
		if (list[j]<list[least]) least = j;
		// #define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))
		temp = list[i];
		list[i] = list[least];
		list[least] = temp;
	}
}

// 삽입 정렬
void InsertionSort(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 BubbleSort(int list[], int n)
{
	int i, j, temp;
	temp = 0;
	for (i = n - 1; i>0; i--)
	{
		for (j = 0; j<i; j++)
		if (list[j]>list[j + 1])
		{
			// #define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))
			temp = list[j];
			list[j] = list[j + 1];
			list[j + 1] = temp;
		}
	}
}

// 합병 정렬; 리스트 합병
void Merge(int list[], int left, int mid, int right)
{
	int i, j, k, l = 0;
	int *sorted;
	i = left; j = mid + 1; k = left;
	sorted = (int *)malloc(sizeof(int)*right);
	/*
		i는 정렬된 왼쪽 리스트에 대한 인덱스
		j는 정렬된 오른쪽 리스트에 대한 인덱스
		k는 정렬될 리스트에 대한 인덱스
		*/
	// 분할 정렬된 list의 합병
	
	while (i <= mid && j <= right)
	{
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}
	if (i > mid)	// 남아 있는 레코드의 일괄 복사
		for (l = j; l <= right; l++)
			sorted[k++] = list[l];
	else			// 남아 있는 레코드의 일괄 복사
		for (l = i; l <= mid; l++)
			sorted[k++] = list[l];
	// 배열 sorted[]의 리스트를 배열 list[]로 재복사	
	for (l = left; l <= right; l++)
		list[l] = sorted[l];
}

// 합병 정렬
void MergeSort(int list[], int left, int right)
{
	int mid;
	if (left < right)
	{
		mid = (left + right) / 2;	// 리스트의 균등 분배
		MergeSort(list, left, mid);	// 부분 리스트 정렬
		MergeSort(list, mid + 1, right);// 부분 리스트 정렬
		Merge(list, left, mid, right);	// 합병
	}
}

// 퀵 정렬; 파티션 분할
int Partition(int list[], int left, int right)
{
	int pivot, temp;
	int low, high;

	low = left;
	high = right + 1;
	pivot = list[left];

	do
	{
		do
			low++;
		while (low <= right && list[low] < pivot);
		do
			high--;
		while (high >= left && list[high] > pivot);
		if (low < high)
		{	// #define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))
			temp = list[low];
			list[low] = list[high];
			list[high] = temp;
		}
	} while (low < high);

	// #define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))
	temp = list[left];
	list[left] = list[high];
	list[high] = temp;

	return high;
}

// 퀵 정렬
void QuickSort(int list[], int left, int right)
{
	if (left < right)
	{
		int q = Partition(list, left, right);
		QuickSort(list, left, q - 1);
		QuickSort(list, q + 1, right);
	}
}

// input.txt파일 생성 함수
void Input(int list[], int n)
{
	FILE *input;
	int file_state;
	int i = 0;

	input = fopen("input.txt", "w");
	if (input == NULL)
		printf("파일 생성에 실패하였습니다.\n");
	for (i = 0; i < n; i++)
		fprintf(input, "%d\n", list[i]);
	file_state = fclose(input);
	if (file_state == EOF)
		printf("파일 닫기 에러\n");
	printf("input.txt에 배열이 저장되었습니다.");
}

// output.txt파일 생성 함수
void Output(int list[], int n)
{
	FILE *output;
	int file_state;
	int i = 0;

	output = fopen("output.txt", "w");
	if (output == NULL)
		printf("파일 에러\n");
	for (i = 0; i < n; i++)
		fprintf(output, "%d\n", list[i]);
	file_state = fclose(output);
	if (file_state == EOF)
		printf("파일 닫기 에러\n");
	printf("output.txt에 배열이 저장되었습니다.");
}


//  실제 정렬함수 호출 관할
void command(int n)
{
	FILE *input;
	clock_t start, finish;	// 시간 측정 변수
	double duration;		// (finish - start)값
	int file_state;
	int command;
	int i, value;
	int *list;
	list = (int *)malloc(sizeof(int)*n);

	input = fopen("input.txt", "r");
	if (input == NULL)
	{
		printf("파일을 읽어오는 데 실패하였습니다.\n");
		exit(1);
	}
	for (i = 0; i < n; i++)
	{
		fscanf(input, "%d\n", &value);	// input.txt에서 1줄씩 읽어옴.
		list[i] = value;	// 배열에 그 값을 대입함.
	}
	file_state = fclose(input);
	if (file_state == EOF)
	{
		printf("파일을 닫을 수 없습니다!\n");
		exit(1);
	}

	printf("\n1 : 선택정렬, 2 : 삽입정렬, 3 : 버블정렬, 4 : 합병정렬, 5 : 퀵정렬");
	printf("\n명령어를 입력하세요 : ");
	scanf("%d", &command);

	start = clock();
	switch (command)
	{
	case 1:
		SelectionSort(list, n);	// 선택정렬
		break;
	case 2:
		InsertionSort(list, n);	// 삽입정렬
		break;
	case 3:
		BubbleSort(list, n);	// 버블정렬
		break;
	case 4:
		MergeSort(list, 0, n - 1);// 합병정렬
		break;
	case 5:
		QuickSort(list, 0, n - 1);// 퀵정렬
		break;
	}
	Output(list, n);
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("%0.3f초가 걸렸습니다.\n\n", duration);
}



int main()
{
	int i;			// loop문 제어변수
	int n = 25000;	// 생성할 난수의 갯수
	int *list;	// 난수값이 저장될 int형 배열
	char cmd;	// input.txt 생성여부 결정
	srand((unsigned)time(NULL));	// 시간에 따라 난수 생성
	list = (int *)malloc(sizeof(int)*n);

	for (i = 0; i<n; i++)	// 난수 생성
		list[i] = rand() % 32768;

	printf("난수를 %d개만큼 생성합니다.\n", n);

	printf("새로 파일을 생성하시겠습니까?(y/n) : ");
	cmd = getchar();
	fflush(stdin);
	if (cmd == 'y')
		Input(list, n);		// 정렬 전 파일(input.txt) 저장

	command(n);
	return 0;
}