(Data Structure) 정렬알고리즘 성능 평가

정렬알고리즘 종류

1. Bubble_sort

2. Insert_sort

3. Select_sort

4. Merge_sort

5. Quick_sort 

 

@소스코드 

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

#define DATA_MAX 50000

int Data[DATA_MAX];

void firstDataInit()
{
	int i;
	for (i = 0; i < DATA_MAX ; i++)
		Data[i] = i;
}

void DataInit()
{
	firstDataInit();

	srand((unsigned int)time(NULL));
	int temp,i,count;
	//parts unranked, part unsorted
	for (i = 0; i < DATA_MAX*3; i++)
	{
		int x = rand() % DATA_MAX;
		int y = rand() % DATA_MAX;
		if (x != y)
		{
			temp = Data[x];
			Data[x] = Data[y];
			Data[y] = temp;
		}
	}

	//parts ranked, parts unsorted
	/*for (count= 0; count < (DATA_MAX / 2) * 3; count++)
	{
		int x = rand() % (DATA_MAX/2);
		int y = rand() % (DATA_MAX/2);
		if (x != y)
		{
			temp = Data[x];
			Data[x] = Data[y];
			Data[y] = temp;
		}
	}
	for (count = 0; count < (DATA_MAX / 2) * 3; count++)
	{
		int x = rand() % (DATA_MAX / 2) + DATA_MAX/2;
		int y = rand() % (DATA_MAX / 2) + DATA_MAX/2;
		if (x != y)
		{
			temp = Data[x];
			Data[x] = Data[y];
			Data[y] = temp;
		}
	}
	*/

	//parts unranked, parts sorted
	/*for (i = 0; i < DATA_MAX / 2; i++)
	{
		temp = Data[i];
		Data[i] = Data[i + DATA_MAX / 3];
		Data[i + DATA_MAX / 3] = temp;
	}
	//parts unranked, one part sorted
	for (count = 0; count < (DATA_MAX / 2) * 3; count++)
	{
		int x = rand() % (DATA_MAX / 2) + DATA_MAX / 2;
		int y = rand() % (DATA_MAX / 2) + DATA_MAX / 2;
		if (x != y)
		{
			temp = Data[x];
			Data[x] = Data[y];
			Data[y] = temp;
		}
	}*/
	
	//parts ranked, one part sorted
	/*for (count = 0; count < (DATA_MAX / 2) * 3; count++)
	{
		int x = rand() % (DATA_MAX / 2) + DATA_MAX / 2;
		int y = rand() % (DATA_MAX / 2) + DATA_MAX / 2;
		if (x != y)
		{
			temp = Data[x];
			Data[x] = Data[y];
			Data[y] = temp;
		}
	}*/






}

void bubbleSort() // average : O(n^2)
{
	int i = 1;
	int last = DATA_MAX;
	for (i = 1; i < DATA_MAX; i++)
	{
		for (int k = 1; k < last-1; k++)
		{
			if (Data[k] > Data[k + 1])
			{
				int temp = 0;
				temp = Data[k];
				Data[k] = Data[k + 1];
				Data[k + 1] = temp;
			}
		}
		last--;
	}	
}

void insertSort()
{
	int i = 0;
	int key;
	int k=0;
	int temp;

	for (i = 1, key = i + 1; i < DATA_MAX-1; i++,key++)
	{
		if (Data[i] > Data[key])
		{
			temp = Data[i];
			Data[i] = Data[key];
			Data[key] = temp;

			for (k = i; k >1; k--)
			{
				if (Data[k - 1] > Data[k])
				{
					temp = Data[k];
					Data[k] = Data[k - 1];
					Data[k - 1] = temp;
				}
			}
		}
	}
}

void insertSort()//best : O(n) average : O(n^2)
{
	int k;
	for (int i = 2; i < DATA_MAX; i++)
	{
		Data[0] = Data[i];
		for (k = i - 1; k > 0 && Data[0]< Data[k]; k--)
		{
			Data[k + 1] = Data[k];
		}
		Data[k + 1] = Data[0];
	}

}

void insertSort()
{
	int k;
	for (int i = 2; i < DATA_MAX; i++)
	{
		Data[0] = Data[i];
		k = i - 1;
		while (Data[0] < Data[k])
		{
			Data[k + 1] = Data[k];
			k--;
		}
		Data[k+1] = Data[0];
	}
}

void BubbleSort()
{
	int n = DATA_MAX -1;
	for (int i = 0; i < DATA_MAX; i++)
	{
		for (int k = i; k < n; k++)
		{
			if (Data[k + 1] < Data[k])
			{
				int temp = Data[k + 1];
				Data[k + 1] = Data[k];
				Data[k] = temp;
			}
		}
		n--;
	}
}

void selectSort()// average : O(n^2)
{
	int i;
	int k;
	int minIndex;
	int temp;

	for (i = 1; i < DATA_MAX; i++)
	{
		minIndex = i;
		for (k = i + 1; k < DATA_MAX; k++)
		{
			if (Data[minIndex] > Data[k])
				minIndex = k;
		}
		temp = Data[minIndex];
		Data[minIndex] = Data[i];
		Data[i] = temp;
	}
}

void print()
{

	for (int i = 0; i < DATA_MAX; i++)
		printf("%d ", Data[i]);
	printf("\n");

}


void SelectSort()
{
	int minIndex;
	
	for (int i = 0; i < DATA_MAX; i++)
	{
		minIndex = i;
		for (int k = DATA_MAX-1; k >= i; k--)
		{
			
			if (Data[minIndex] > Data[k])
			{
				minIndex = k;
			}
			int temp = Data[minIndex];
			Data[minIndex] = Data[i];
			Data[i] = Data[minIndex];
		}
	}



}

void quickSort(int left, int right)
{
	int pivot, i,j, temp;
	if (left < right)
	{
		do {
			i = left;
			j = right + 1;
			pivot = Data[left];

			do  i++; while (Data[i] < pivot && i < j);
			do  j--; while (Data[j] > pivot && i < j);

			if (i < j)
			{
				int temp = Data[i];
				Data[i] = Data[j];
				Data[j] = temp;
			}
		} while (i < j);
		temp = Data[j];
		Data[j] = Data[left];
		Data[left] = temp;

	}
	


}

void quickSort(int left, int right)  //best : O(n*log2(n)) , worst : O(n^2)
{
	int pivot, i, j,temp;
	
	if (left < right)
	{
		i = left; j = right + 1;
		pivot = Data[left];

		do {
			do i++; while (Data[i] < pivot); //&& i < right
			do j--; while (Data[j] > pivot); //&& j > left
			if(i < j)
			{
				temp = Data[i];
				Data[i] = Data[j];
				Data[j] = temp;
			}
		} while (i < j);
		temp = Data[j];
		Data[j] = Data[left];
		Data[left] = temp;
		quickSort(left, j - 1);
		quickSort(j + 1, right);
	}

}

void quickSort(int list[], int left, int right)
{
	int i, j, temp;
	int pivot = list[left];
	if (left < right)
	{
		i = left;
		j = right + 1;
		do
		{
			do i++; while (list[i] <= pivot);
			do j--; while (list[j] >= pivot);

			if (i < j)
			{
				temp = list[i];
				list[i] = list[j];
				list[j] = temp;
			}
		} while (i < j);

		temp = list[left];
		list[left] = list[j];
		list[j] = temp;

		quickSort(list, left, j - 1);
		quickSort(list, j + 1, right);
	}


}


void merge(int m,int mid,int n) //average : O(n*log2(n))
{
	int Sorted[DATA_MAX] = { 0 ,};
	int i, j, k, t;
	i = m;
	j = mid + 1;
	k = m;

	while (i <= mid && j <= n)
	{
		if(Data[i]<=Data[j]) Sorted[k++] = Data[i++];
		else Sorted[k++] = Data[j++];
	}

	if (i > mid)
		for (t = j; t <= n; t++, k++)
			Sorted[k] = Data[t];
	else
		for (t = i; t <= mid; t++, k++)
			Sorted[k] = Data[t];

	for (t = m; t <= n; t++) Data[t] = Sorted[t];
}

void mergeSort(int m,int n)
{
	int mid;
	if (m < n)
	{
		mid = (m + n) / 2;
		mergeSort(m, mid);			//before the middle
		mergeSort(mid + 1, n);		//after the middle
		merge(m, mid, n);			//merge
	}
}

//i : 정렬될 왼쪽 배열 인덱스
//j : 정렬될 오른쪽 배열 인덱스
//k : 임시 정렬 배열 인덱스
void merge(int list[], int left, int mid,int right)
{
	int i, j, k, t;
	i = left;
	j = mid + 1;
	k = left;
	int Sorted[DATA_MAX] = {0,};

	while (i <= mid && j <= right)
	{
		if (list[i] <= list[j]) Sorted[k++] = list[i++];
		else Sorted[k++] = list[j++];
	}

	if (i > mid)
		for (t = j; t <= right; t++)
			Sorted[k++] = list[t];
	else
		for (t = i; t <= mid; t++)
			Sorted[k++] = list[t];

	for (k = left; k <= right; k++)
		list[k] = Sorted[k];

}

*/
int main()
{
	
	//printf("parts unranked, one part sorted\n");
	//printf("parts unranked, parts sorted\n");
	//printf("parts ranked, One part sorted\n");
	//printf("parts ranked,parts unsorted\n");
	printf("parts unranked,parts unsorted\n");
	
	DataInit();
	//print();
	clock_t start = clock();
	bubbleSort();
	clock_t end = clock();
	printf("Bubble Time : %lf\n", (double)(end - start) / CLOCKS_PER_SEC); // second

	DataInit();
	clock_t start2 = clock();
	insertSort();
	clock_t end2 = clock();
	printf("Insert Time : %lf\n", (double)(end2 - start2) / CLOCKS_PER_SEC); // second
	
	DataInit();
	clock_t start3 = clock();
	selectSort();
	clock_t end3 = clock();
	printf("Select Time : %lf\n", (double)(end3 - start3) / CLOCKS_PER_SEC); // second
	
	DataInit();
	clock_t start5 = clock();
	mergeSort(1, DATA_MAX - 1);
	clock_t end5 = clock();
	printf("Merge Time : %lf\n", (double)(end5 - start5) / CLOCKS_PER_SEC); // second


	DataInit();
	clock_t start4 = clock();
	quickSort(1,DATA_MAX-1);
	clock_t end4 = clock();
	printf("Quick Time : %lf\n", (double)(end4 - start4) / CLOCKS_PER_SEC); // second
	
	



	return 0;
}