[C언어] 정렬 알고리즘 (삽입정렬, 퀵정렬, 합병정렬)

정렬 알고리즘 중 삽입정렬, 퀵정렬, 합병정렬에 대해 알아보자.

 

1. 삽입정렬(Insertion sort)

삽입정렬은 정렬된 수와 정렬할 수를 나누어서 모든 수가 정렬된 수가 될 때까지 과정을 반복하는 알고리즘이다. 

 

삽입정렬의 과정은 다음과 같다.

1. 정렬된 수와 정렬할 수로 섹션을 나눈다. (처음에는 정렬된 수가 없기 때문에 가장 정렬할 수의 가장 첫 번째 수를 둔다.)

2. 정렬할 수를 들어 올려서 (실제로 들어 올리는 건 아니지만 그렇다고 생각하고) 정렬된 수와 비교한다. 

정렬된 수보다 작으면 정렬된 수를 한 칸 뒤로 보내고 그 자리에 들어 올린 수를 둔다. 

비교가 끝나면 그 수는 정렬된 수에 포함된다.

3. 모든 수가 정렬된 수가 될 때까지 위 과정을 반복한다. 

 

참고 유튜브 링크: https://www.youtube.com/watch?v=fIe7gdgMvMU 

 

#include <stdio.h>

#define SIZE 10

void insertion_sort(int[], int);
void print_array(int[], int);

int main(void) {

	int arr[SIZE] = { 10, 8, 3, 7, 2, 6, 4, 9, 1, 5 };

	print_array(arr, SIZE); // 정렬 전 배열 출력
	insertion_sort(arr, SIZE); // 삽입 정렬
	print_array(arr, SIZE); // 정렬 후 배열 출력
}

void print_array(int arr[], int size) {
	for (int i = 0; i < size; i++) {
		if (arr[i] == 0) break;
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void insertion_sort(int arr[], int size) {
	int temp; // 들어 올린 수
	
	for (int i = 1; i < size; i++) {
		temp = arr[i];
		for (int j = i - 1; j >= 0; j--) {
			if (arr[j] > temp) {
				arr[j + 1] = arr[j];
			}
			else break;
			arr[j] = temp;
		}
	}
}

 

2. 퀵정렬(Quick sort)

퀵정렬은 두 기준점을 잡고 피봇과 비교하며 수를 정렬하는 방법이다. 

 

두 기준점은 배열의 가장 왼쪽과 가장 오른쪽으로 잡는다. 이해하기 쉽게 배열의 가장 왼쪽은 빨간 점, 가장 오른쪽은 파란 점이라고 생각하자. 빨간 점은 작은 수의 위치를 의미하고 파란 점은 큰 수의 위치를 의미한다. 

 

피봇의 선정은 ①배열의 첫 번째 값 or마지막 값 or중간값으로 정하는 방법과 ②랜덤으로 정하는 방법이 있다. 어떤 방법이 가장 빠른지에 대해서는 아직 정해진 것이 없으며 관련 논문이 많다고 하니 참고하면 좋을 것 같다.

 

퀵정렬의 피봇을 배열의 첫 번째 값으로 잡았을 때의 과정은 다음과 같다. 

1. 피봇을 배열의 첫 번째 값으로 잡는다. 배열의 첫 번째 값에는 빨간 점을 마지막 값에는 파란 점을 위치시킨다. 

2. 피봇을 파란 점이 위치한 수와 비교한다. 

피봇이 파란 점이 위치한 수보다 작다면 파란 점을 한 칸 왼쪽으로 이동시킨다. 

피봇이 파란점이 위치한 수보다 크다면 파란 점이 위치한 수를 빨간 점으로 이동시킨다. 이때부터는 빨간 점과 피봇을 비교한다. 

3. 2를 반복하면 빨간 점과 파란 점이 만나는 부분이 생긴다. 그 부분이 피봇의 고정 위치이다.

4. 위 과정을 반복하여 모든 수의 고정 위치가 정해지면 정렬 끝!

 

참고 유튜브 링크 : https://www.youtube.com/watch?v=S2c4zAGgVgI 

 

3. 합병정렬(merge sort)

합병 정렬은 분할, 정복, 결합 과정을 거쳐 정렬을 하는 알고리즘이다.

 

분할(Divide)은 배열을 같은 크기의 2개의 배열로 분할하는 과정이다.

정복(Conquer)은 각 부분 배열을 정렬하는 과정이다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.

결합(Combine): 정렬된 부분 배열들을 다시 하나의 배열로 합병하는 과정이다. 

 

합병 정렬의 과정은 다음과 같다. 

1. 배열을 절반으로 잘라 두 부분으로 나눈다. (분할)

2. 각 부분을 재귀적으로 합병 정렬을 이용해 정렬한다. (정복)

3. 두 부분의 배열을 다시 하나의 정렬된 배열로 합병한다. (결합)