알고리즘 : 정렬이란? (C++로 구현)

정렬 알고리즘이란?

불규칙한 데이터들을 정렬해야 할 때, 상황에 맞는 알고리즘을 사용하여 문제를 해결할 수 있다. 예를 들어, 특정 숫자를 찾아야 할 때 정렬된 데이터들 속에서 찾는 것과 정렬되지 않은 데이터들에서 찾는 것은 차이가 발생한다. (이진탐색을 사용할 수 있고 없고가 결정됨)

 

정렬 알고리즘들을 비교하기 위해 Big O 표기법을 사용하여 시간복잡도를 나타낼 것이므로 시간복잡도에 대한 지식이 아예 없다면 아래 짧은 포스팅을 읽고 오는 것을 추천한다.

 

https://shine-slowly.tistory.com/33

알고리즘: 시간 복잡도란

 

 

버블 정렬(Bubble Sort)

인접한 두 항목의 값을 비교해서 서로의 값을 교환하는 방식이다. 인접한 2개의 값이 크기 순서대로 되어 있지 않으면 서로 교환한다. 버블 정렬은 거의 모든 상황에서 최악의 성능을 보여주지만 이미 정렬된 자료에서는 1번만 순회하면 되기 때문에 최선의 성능을 보여주게 된다. 

 

1. 0번째 원소와 1번째 원소를 비교 후 정렬
2. 1번째 원소와 2번째 원소를 비교 후 정렬
...
n. n-1번째 원소와 n번째 원소를 비교 후 정렬

위 그림에서도 알 수 있듯이, 가장 큰 값은 1회 처리에서 가장 뒤에 위치하게 된다.

 

void bubbleSort(int list[], int n) { //n은 정렬의 크기
	int i, j, temp;
	for (i = n - 1; i > 0; i--) { // 맨 뒤부터 각자 자리를 찾아가게 된다
		for (j = 0; j < i; j++) {
			if (list[j] > list[j + 1]) {
				swap(list[j], list[j + 1]);
			}
		}
	}
}

시간 복잡도를 계산해보면, for문이 (n-1)+(n-2)+...+3+2+1번 반복되므로 n(n-1)/2로 O(n^2)가 된다.

 

위 코드를 실행시키면 이와 같이 동작하게 될 것이다.

 

 

 

선택 정렬(Selection Sort)

가장 작은 값을 찾아 첫번째 값과 교환하고, 첫번째 값을 제외한 부분에서 최소값을 찾고 두번째 값과 교환한다. 첫번째, 두번쨰 값을 제외한 나머지에서 또 최소값을 찾고 교환하며 반복한다.

 

1. 0 번째 ~ n 번째 중 가장 작은 값을 찾아 0번째와 교환
2. 1 번째 ~ n 번째 중 가장 작은 값을 찾아 1번째와 교환
...
n. n-1번째 ~ n 번째 중 가장 작은 값을 찾아 n-1번째와 교환

이와 같은 방식으로 동작한다.

 

void selectionSort(int list[], int n) { //n은 정렬의 크기
	for (int i = 0; i < n-1; i++)
	{
		int minIndex = i;
		for (int j = i+1; j < n; j++) // 최소값 찾기
		{
			if (list[j] < list[minIndex])
				minIndex = j;
		}

		if (i != minIndex) {
			swap(list[i], list[minIndex]);
		}
	}
}

n-1+n-2+n-3+...+2+1번 for문에서 비교가 반복되게 된다. n(n-1)/2로 O(n^2)가 선택정렬의 시간복잡도이다.

 

위 코드를 실행시키면 이와 같은 결과가 나올 것이다.

 

 

 

삽입 정렬(Insertion Sort)

모든 요소를 앞에서부터 차례대로 정렬된 부분과 비교해서 자신의 위치를 찾아 삽입하는 방식이다. 두 번째 값부터 시작하여 앞에 있는 자료랑 비교해서 어디에 끼워넣을지 정하고 지정한 자리에 삽입한다.

 

1. 0 ~ 1번째 값 중 1번 인덱스 값이 들어갈 곳을 찾아 넣는다
2. 0 ~ 2번째 값 중 2번 인덱스 값이 들어갈 곳을 찾아 넣는다
...
n. 0 ~ n번째 값 중 n번 인덱스 값이 들어갈 곳을 찾아 넣는다

이와 같이 동작한다.

 

void insertionSort(int list[], int n) { //n은 정렬의 크기
	for (int i = 1; i < n; i++)
	{
		int temp = list[i];
		int j;
		for (j = i-1; j >= 0 && list[j] > temp; j--)
		{
			list[j + 1] = list[j];
		}
		list[j + 1] = temp;

	}
}

list가 {5, 4, 3, 2, 1}인 경우를 생각해보면 먼저 4는 5와 비교를 1번하게 된다. 그 다음 3은 5, 4와 2번 비교하게 된다. 2 또한 5, 4, 3과 모두 비교를 해보아야 한다. 이렇게 최악의 상황이 될 경우 n-1+n-2+...+2+1이 되어 n(n-1)/2로 O(n^2)가 된다.

하지만 모두 정렬이 되어 있는 형태에서는 1번씩 비교하고 끝나게 된다. 그럼 O(n)이 된다.

 

 

 

 

병합 정렬(Merge Sort)

리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 보고, 그렇지 않으면 정렬되지 않은 리스트를 절반으로 나눈다. 나눈 각 리스트를 재귀적으로 정렬한다. 두 리스트를 하나로 합친다.

먼저 같은 크기의 2개의 부분 배열로 나누고 부분 배열을 정리한다. 부분 배열의 크기가 작지 않으면 다시 분할한다. 정렬된 부분 배열을 하나의 배열로 합친다. 

 

위 과정은 두 리스트를 합치는 과정이다. 2개의 리스트의 값을 처음부터 하나씩 비교해서 더 작은 값을 새로운 리스트에 옮긴다. 둘 중에서 하나의 리스트가 끝나게 되면 나머지 리스트를 새로운 리스트에 그대로 붙여넣는다. 

 

int sorted[8];
void merge(int list[], int left, int mid, int right) {
	int i = left;
	int j = mid + 1;
	int k = left;
	while (i <= mid && j <= right) {
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}

	if (i > mid) { // 오른쪽 부분 정렬이 남아있음
		for (int l = j; l <= right; l++)
		{
			sorted[k++] = list[l];
		}
	}
	else { // 
		for (int l = i; l <= mid; l++)
		{
			sorted[k++] = list[l];
		}
	}
	for (int l = left; l <= right; l++) { // 정렬된 부분을 list에 붙여넣기
		list[l] = sorted[l];
	}
}

void mergeSort(int list[], int left, int right) {
	if (left < right) { // 개수가 1개 될때까지 재귀
		int mid = (left + right) / 2; // 가운데 찾기
		mergeSort(list, left, mid); 
		mergeSort(list, mid+1, right);
		merge(list, left, mid, right);
	}
}

분할 단계에서는 재귀 함수를 호출하므로 비교 연산 또는 이동 연산과 같은 연산이 수행되지 않는다. 병합 단계에서 오른쪽 그림과 같이 n번씩 비교를 하게 되며 순환 호출의 깊이는 n/2^i만큼씩 크기가 작아지므로 logn이 된다. 즉 시간복잡도는 O(nlogn)이다.

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

합병정렬은 이 티스토리를 참고 했으며 매우 자세히 설명되어있으므로 부족한 부분이 있다면 읽어보는 것을 추천한다.

 

 

 

 

Quick Sort (퀵 정렬)

분할 정복 알고리즘의 하나로 매우 빠른 수행 속도를 자랑한다. 분할 정복 방법이란 문제를 2개의 문제로 분리하고 해결한 다음에 결과를 모아서 원래 문제를 해결하는 전력이다. 병합 정렬과 다르게 퀵 정렬은 비균등하게 분할을 하게 된다.

1. 리스트 안에서 pivot 하나를 고른다.
2. pivot을 기준으로 작은 요소들은 다 왼쪽으로, 큰 요소는 다 오른쪽으로 옮겨진다.
3. pivot을 제외한 부분 리스트에서 다시 pivot을 정하고 반복한다.
4. 부분 리스트의 크기가 0이나 1이 될 때까지 반복한다.

 

위 그림은 pivot을 리스트의 첫번째 값으로 한 경우이다. (random 하게 설정해도 됨)

 

int partition(int list[], int left, int right) { // 정렬
	// list[left...pivot-1]와 list[pivot+1...right]
	int pivot, temp;
	int low, high;
	low = left;
	high = right + 1;
	pivot = list[left];
	do {
		// low와 high가 교차
		do {
			// list[low]가 pivot 보다 작으면 low를 계속 증가
			// 처음에는 무조건 low++이니까 left+1부터 제대로 된 비교 시작ㅇ
			low++;
		} while (low <= right && list[low] < pivot);
		
		do {
			// list[high]가 pivot 보다 크면 high를 계속 감소
			high--;
		} while (high >= left && list[high] > pivot);

		if (low < high) { 
			// 모두 pivot보다 큰 경우, low는 right보다 커져서 빠져나오게 됨
			// 이런 경우 low가 high보다 커짐 => 교차했다
			swap(list[low], list[high]);
		}
	} while (low < high);

	swap(list[left], list[high]); // 교차했을 경우 pivot이랑 pivot보다 작은 값이랑 교환

	return high; // pivot의 위치
}
void quickSort(int list[], int left, int right) {
	if (left < right) { // 리스트 크기가 1보다 클 경우만
		int p = partition(list, left, right);
		quickSort(list, left, p - 1); // 피벗 바로 앞
		quickSort(list, p + 1, right); // 피벗 바로 뒤
	}
}

분할하여 푸는 알고리즘은 재귀 함수 (순환 함수)를 사용하여 구현하게 된다.

 

퀵 정렬에서 pivot 설정이 오른쪽과 같이 되는 경우의 최악의 경우이다. 데이터가 2배씩 주는것이 아닌 1씩 줄어들어 깊이가 n이 되고 각 호출마다 데이터 개수만큼 비교하게 되어서 O(n^2)이 된다.

레코드 개수가 n이라고 했을 때 개수가 2배씩 줄어들게 된다. 각 호출당 그 개수만큼 비교하게 되므로 O(nlogn)이 된다.

퀵소트가 c++에서 sort()함수에서 사용되는 정렬방식이다

 

 

Algorithm	Time	Stable	In-place
Bubble sort	O(n^2)	Yes	Yes
Selection sort	O(n^2)	No	Yes
Insertion sort	O(n^2)	Yes	Yes
Merge sort	O(nlogn)	Yes	No
Quick sort	O(nlogn)	No or Yes	Yes or No

Stable이란 {1, 2, 1, 2}와 같은 배열일 때 정렬 후 가장 첫번째에 있던 1 다음에 세번째에 있던 1이 오고, 그다음에 두번째에 있던 2, 마지막으로 네번째에 있던 2가 오는지이다. 

In-place는 추가 배열이 필요한지, 혹은 필요하지 않은지이다.

 

 

 

쉘 정렬 (Shell Sort)

삽입정렬을 간단하게 변형한 정렬이다. 멀리 떨어진 원소끼리 교환이 가능하게 하여 정렬 속도를 향상시켰다. 

정렬해야할 리스트의 각 k번째 요소를 추출하여 부분 리스트를 만든다. 간격의 초기값은 [정렬할값개수/2]이다. 생성된 부분리스트 개수는 k와 같다. (k를 gap이라고도 한다)

1. k = 정렬할 값의 수 /2
2. 각 회전마다 k를 절반으로 줄인다. 각 회전에 반복될때마다 부분리스트에 속하는 값들이 증가한다.
3. k가 1이 될 때까지 반복한다

 

혹은 h-정렬 화일을 이용하기도 한다. 증거 순서의 예는 1093, 364, 121, 40, 13, 4, 1이다. 

 

개수가 10이므로 k는 5가 된다. 간격이 5인 부분리스트를 만든다. 각 리스트마다 삽입 정렬로 정렬을 하게 된다. 이를 반복해서 k가 1일 때까지 반복하면 된다.

 

void insertionSort(int list[], int first, int last, int gap) {
	int key;
	for (int i = first+gap; i <= last; i+=gap)
	{
		key = list[i]; // i번째 값

		// 삽입 정렬
		int j;
		for (j = i - gap; j >= first && list[j] > key; j -= gap)
		{
			list[j + gap] = list[j]; // gap 오른쪽 만큼 이동
		}
		list[j + gap] = key;
	}
}
void shellSort(int list[], int n) {
	for (int gap = n / 2; gap > 0; gap/=2)
	{
		if ((gap % 2) == 0)
			gap++; // gap을 홀수로 설정

		for (int i = 0; i < gap; i++) // 부분리스트 개수는 gap과 같다
		{
			insertionSort(list, i, n - 1, gap);
		}
	}
}

시간복잡도를 계산하면 O(n^1.5)가 된다고 한다. 앞서 말했듯이 shell sort는 굉장히 여러가지로 구현할 수 있기 때문에 딱 하나만 찝을 수는 없다.

 

 

 

 

 

힙 정렬(Heap Sort)

힙 정렬에 대해 설명하기 전에 Heap이 무엇인지 설명하도록 하겠다.

힙이란 우선순위 큐(priority queue)의 일종이다. 우선순위 큐란 입력된 값들이 얼정한 우선순위를 가지고 출력될 수 있는 자료구조이다. 

힙은 이진 트리 구조로 각 노드의 우선 순위가 그 노드의 자식들의 우선순위보다 높거나 같으면 최대 힙, 작거나 같으면 최소 힙이다. 힙은 항상 완전 이진 트리 구조로 마지막 레벨은 왼쪽부터 오른쪽으로 차례대로 채워져 있어야 한다.

 

새로운 요소의 힙은 마지막 위치, 가장 오른쪽에 새 노드를 추가한다. 삽입된 노드와 부모 노드를 비교하고 새로운 노드가 부모 노드보다 크면 (최대 힙의 경우) 새 노드와 부모노드의 위치를 교환한다.

 

힙에서 값을 제거할 때는 루트 값을 제거한다. 루트를 제거한 후에 트리의 맨 끝이 있는 값이 루트로 올라간다. 새롭게 채워진 루트 노드를 기준으로 자식 노드와 비교를 진행한다. 2개의 자식 노드 중 우선 순위가 더 높은 노드를 선택해서 비교하게 된다.

 

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog

힙을 구현하는 방법은 위 티스토리에 자세히 설명되어있어서 첨부하였다.

 

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog

코드 구현은 일단 시간이 없어서 티스토리를 첨부하고 나중에 힙정렬 관련 문제가 나오면 자세한 설명을 추가하도록 하겠다.

힙 정렬의 시간복잡도는 O(nlogn)이 된다.