정렬 알고리즘

구현하고 있는 모든 정렬 알고리즘은 오름차순 을 기본으로 작성 하였습니다.

 

1. 선택정렬(selectionSort)

 

원리: 0번째 인덱스 부터 시작해서 배열의 모든 원소를 비교해서 가장 작은 원소를 교환하는 방식으로 정렬을 합니다.

void swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void selectionSort(int* int_array, int size) {
	for (int i = 0; i < size - 1; i++) 
	{
		int min = i;
		for (int j = i + 1; j < size; j++)
		{
			if (int_array[min] > int_array[j]) min = j;
		}

		swap(&int_array[min], &int_array[i]);
	}
}

 

시간 복잡도

최선	평균	최악
O(n^2)	O(n^2)	O(n^2)

 

 

2. 버블정렬(bubbleSort)

원리: 0번째 인덱스 부터 시작해서 다음 인덱스와 비교해서 오름차순 일 경우 오른쪽 값이 크다면 교환합니다. 동일한 방식으로 인덱스를 1 씩 증가하면서 진행하면 마지막 인덱스 부터 순차적으로 정렬이 진행됩니다.

void swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void bubbleSort(int* int_array, int size) {
	for (int i = 1; i < size; i++) {
		int swapped = 0;
		for (int j = 0; j < size - i; j++) {
			if (int_array[j] > int_array[j + 1]) {
				swap(&int_array[j], &int_array[j + 1]);
				swapped = 1;
			}
		}
		if (!swapped) return;
	}
}

***위 코드의 경우 이미 정렬이 되어 있는 경우에는 함수를 바로 종료시키고 있습니다.***

 

시간 복잡도

최선	평균	최악
O(n)	O(n^2)	O(n^2)

 

 

3. 삽입정렬(insertitonSort)

원리: 0번째 인덱스의 값은 이미 정렬되었다고 보고 순차적으로 1번째 인덱스 부터 앞의 인덱스와 비교하면서 자신의 위치를 한칸씩 확인하면서 자신보다 큰 값은 반대 방향으로 한칸씩 이동 시키면서 자신보다 작은 값이 나오면 삽입하는 방식 입니다.

마치 순위를 가르는 경기에서 점수에 따라 삽입되는 방식과 동일하다고 볼 수 있습니다.

void insertitonSort(int* int_array, int size) {
	
	for (int i = 1; i < size; i++) {
		int temp = int_array[i];
		int j = i - 1;
		while (j >= 0 && int_array[j] > temp) {
			int_array[j + 1] = int_array[j];
			j--;
		}
		int_array[j + 1] = temp;
	}
}

 

시간 복잡도

최선	평균	최악
O(n)	O(n^2)	O(n^2)

이 알고리즘은 정렬이 이미 되어있는 경우 순차적으로 비교하고 삽입을 위해 앞의 모든 원소를 이동시킬 필요가 없기 때문에 최선의 경우 O(n) 의 시간 복잡도를 가질 수 있습니다.

 

또한 이 알고리즘의 특성상 삽입이 많기 때문에 배열 보다는 포인터로 연결되어 있는 링크드리스트 로 구현하는것이 더 효율적일 수 있습니다,

 

 

4. 퀵정렬(quickSort)

원리: 이 알고리즘은 피벗(기준값) 을 잡고 기준값 보다 왼쪽에는 작은값만 놓고 오른쪽에는 큰 값만 놓습니다.

그리고 피봇을 중심으로 양쪽에 또 다른 피봇을 잡아서 동일한 방식으로 진행을 하면 정렬이 완료 됩니다.

int partition(int* arr, int start, int end) {
	int pivot = arr[(start + end) / 2];
	int i = start;
	int j = end;

	while (i <= j) {
		while (arr[i] < pivot) i++;
		while (arr[j] > pivot) j--;
		if (i <= j) {
			swap(&arr[i], &arr[j]);
			i++;
			j--;
		}
	}
	return i;
}

void recursiveQuickSort(int* arr, int start, int end) {
	if (start < end) {
		int pi = partition(arr, start, end);
		recursiveQuickSort(arr, start, pi - 1);
		recursiveQuickSort(arr, pi, end);
	}
}

void quickSort(int* int_array, int size) {
	recursiveQuickSort(int_array, 0, size - 1);
}

 

시간 복잡도

최선	평균	최악
O(n log n)	O(n log n)	O(n^2)

이 알고리즘의 핵심은 피벗을 기준으로 양쪽에서 계속 동일한 방법으로 정렬을 시키는 것이 핵심 입니다.

하지만 피벗을 어떤 값으로 잡는지에 따라 시간이 달라지게 됩니다. 만약 모든 피벗을 배열의 값들 중 가장 큰 값 또는 가장 작은 값으로 고르게 된다면 한쪽에서만 수행이 되기 때문에 최 악의 경우가 발생하게 됩니다.

 

5. 병합정렬(mergeSort)

원리: 배열을 반으로 나누고 나누어진 배열을 또 반으로 나누는것을 반복하면서1개의 요소로 분할한 후 2개의 값을 비교해서 임시 배열에 작은값 또는 큰 값 먼저 넣고 이를 다시 반대로 결합하여 이 과정을 반복적으로 수행하고 임시 배열에 있는 값을 원본에 복사하는 방식으로 진행이 됩니다.

void merge(int* int_array, int mid, int start, int end) {
	int i = start, j = mid + 1;
	int k = 0;
	int tempSize = end - start + 1;
	int* temp = malloc(tempSize * sizeof(int));

	if (temp == NULL) {
		return;
	}

	while (i <= mid && j <= end) {
		if (int_array[i] < int_array[j]) {
			temp[k++] = int_array[i++];
		}
		else {
			temp[k++] = int_array[j++];
		}
	}

	while (i <= mid) temp[k++] = int_array[i++];
	while (j <= end) temp[k++] = int_array[j++];

	for (i = start, k = 0; i <= end; i++, k++) {
		int_array[i] = temp[k];
	}

	free(temp);
}
void mergeSort(int* int_array, int start, int end) {
	if (start < end) {
		int mid = (start + end) / 2;
		mergeSort(int_array, start, mid);
		mergeSort(int_array, mid + 1, end);
		merge(int_array, mid, start, end);
	}
}

 

시간 복잡도

최선	평균	최악
O(n log n)	O(n log n)	O(n log n)

병합정렬 은 퀵정렬과 속도는 비슷하지만 최 악의 경우에도 동일한 O(n log n) 의 시간복잡도로 성능면에서는 더 안정적인 정렬 알고리즘 입니다.

하지만 단점은 임시 배열을 생성해야 하기 때문에 메모리 사용량이 높다는 단점이 있습니다.

 

	최선	평군	최악
선택 정렬	O(n^2)	O(n^2)	O(n^2)
버블 정렬	O(n)	O(n^2)	O(n^2)
삽입 정렬	O(n)	O(n^2)	O(n^2)
퀵 정렬	O(n log n)	O(n log n)	O(n^2)
병합 정렬	O(n log n)	O(n log n)	O(n log n)

 

위 알고리즘은 안정정렬, 불안정정렬 로 구분할 수 있습니다.

안정 정렬은 동일한 값이 있을경우 원소가 정렬될 때 순서가 바뀌지 않고 유지됩니다.

불안정 정렬은 동일한 값이 있으면 순서가 바뀔 수 있습니다.

 

위 표에서 빨간색 으로 표시된 알고리즘이 불안정 정렬 알고리즘 입니다.

 

정렬 알고리즘 성능비교

테스트 환경

OS: 윈도우11

RAM: 16GB(실제용량 15.7GB)

CPU: Intel Core i7 2.8GHz

 

모든 알고리즘을 (100,000, 200,000, 300,000, 400,000, 500,000) 개의 인덱스에

랜덤값을 넣어서 각각10번씩 실행시킨 후 Best, Avg, Worst 를 측정하였습니다.

 

 

 

버블정렬과 삽입정렬은 BestCase 와 AvgCase 가 거의 비슷하여 겹쳐져서 잘 안보입니다.

 

시간복잡도와 거의 비슷하게 나온거 같습니다.

 

버블정렬의 경우 정렬과정에서 이미 다 되어있다면 조기종료를 하는 코드가 있기 때문에 AvgCase 와 BestCase 가 비슷하게 나온거 같습니다.

 

테스트 코드

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


void swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}


//선택정렬
void selectionSort(int* int_array, int size) {
	for (int i = 0; i < size - 1; i++) 
	{
		int min = i;
		for (int j = i + 1; j < size; j++)
		{
			if (int_array[min] > int_array[j]) min = j;
		}

		swap(&int_array[min], &int_array[i]);
	}
}

//버블정렬
void bubbleSort(int* int_array, int size) {
	for (int i = 1; i < size; i++) {
		int swapped = 0;
		for (int j = 0; j < size - i; j++) {
			if (int_array[j] > int_array[j + 1]) {
				swap(&int_array[j], &int_array[j + 1]);
				swapped = 1;
			}
		}
		if (!swapped) return;
	}
}

//삽입정렬
void insertitonSort(int* int_array, int size) {
	
	for (int i = 1; i < size; i++) {
		int temp = int_array[i];
		int j = i - 1;
		while (j >= 0 && int_array[j] > temp) {
			int_array[j + 1] = int_array[j];
			j--;
		}
		int_array[j + 1] = temp;
	}
}

//선택정렬
int partition(int* arr, int start, int end) {
	int pivot = arr[(start + end) / 2];
	int i = start;
	int j = end;

	while (i <= j) {
		while (arr[i] < pivot) i++;
		while (arr[j] > pivot) j--;
		if (i <= j) {
			swap(&arr[i], &arr[j]);
			i++;
			j--;
		}
	}
	return i;
}

void QuickSort(int* arr, int start, int end) {
	if (start < end) {
		int pi = partition(arr, start, end);
		QuickSort(arr, start, pi - 1);
		QuickSort(arr, pi, end);
	}
}

//병합정렬
void merge(int* int_array, int mid, int start, int end) {
	int i = start, j = mid + 1;
	int k = 0;
	int tempSize = end - start + 1;
	int* temp = malloc(tempSize * sizeof(int));

	if (temp == NULL) {
		return;
	}

	while (i <= mid && j <= end) {
		if (int_array[i] < int_array[j]) {
			temp[k++] = int_array[i++];
		}
		else {
			temp[k++] = int_array[j++];
		}
	}

	while (i <= mid) temp[k++] = int_array[i++];
	while (j <= end) temp[k++] = int_array[j++];

	for (i = start, k = 0; i <= end; i++, k++) {
		int_array[i] = temp[k];
	}

	free(temp);
}
void mergeSort(int* int_array, int start, int end) {
	if (start < end) {
		int mid = (start + end) / 2;
		mergeSort(int_array, start, mid);
		mergeSort(int_array, mid + 1, end);
		merge(int_array, mid, start, end);
	}
}

int arr_size[5] = {100000, 200000, 300000, 400000, 500000};
char* name[5] = { "selectionSort", "bubbleSort", "insertitonSort", "QuickSort", "mergeSort" };
int main() {
	srand(time(NULL));
	for (int type = 0; type < 5; type++) {
		printf("%s 테스트 시작\n", name[type]);
		for (int testCase = 0; testCase < 5; testCase++) {

			printf("인덱스 개수: %d\n", arr_size[testCase]);

			int* p_intArray = (int*)malloc(sizeof(int) * arr_size[testCase]);
			if (p_intArray == NULL) return 1;

			for (int i = 0; i < arr_size[testCase]; i++) {
				p_intArray[i] = rand() % arr_size[testCase];
			}
			//==================================

			float min = 1000000000, max = 0, avg = 0;

			for (int count = 0; count < 10; count++) {
				clock_t start, finish;
				double duration;

				start = clock();

				switch (type) {
				case 0: selectionSort(p_intArray, arr_size[testCase]); break;
				case 1: bubbleSort(p_intArray, arr_size[testCase]); break;
				case 2: insertitonSort(p_intArray, arr_size[testCase]); break;
				case 3: QuickSort(p_intArray, 0, arr_size[testCase] - 1); break;
				case 4: mergeSort(p_intArray, 0, arr_size[testCase] - 1);
				}


				finish = clock();
				duration = (double)(finish - start) / CLOCKS_PER_SEC;

				if (min > duration) {
					min = duration;
				}
				if (max < duration) {
					max = duration;
				}
				if (count > 0) {
					avg += duration;
					avg /= 2;
				}
				else {
					avg = duration;
				}
			}

			printf("Test: %d | 최선: %f, 최악: %f, 평균: %f\n", testCase, min, max, avg);

			free(p_intArray);
		}
		printf("=========================\n\n");
	}
	printf("테스트 종료\n");
	return 0;
}