[열혈자료구조] 10강. 정렬(sorting) (1)

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

 

1부터 N까지의 수가 한 줄로 무작위 순서로 서 있다. 이들을 크기 순서로 세우는 최적의 알고리즘은 무엇일까? 본 포스팅에서는 각종 정렬 알고리즘을 <열혈자료구조>교재를 바탕으로 정리해보고자 한다.

 

정렬 알고리즘의 성능은 비교의 횟수와 이동의 횟수가 결정한다. 그리고 이를 기준으로 Big-O notation을 정한다.

 

1. 버블 정렬(Bubble Sorting)

버블 정렬은 연속한 두 개의 항을 비교하여, 앞의 것이 크기가 크면 순서를 바꾸고, 뒤의 것이 크면 순서를 유지하는 방법이다. 

앞에서부터 뒤로 훑는 이 과정을 모든 수가 정렬될 때까지 반복한다. 버블 정렬의 코드는 아래와 같다.

#include <stdio.h>

void BubbleSort(int arr[], int n)
{
	int i, j;
	int temp;

	for(i=0; i<n-1; i++)
	{
		for(j=0; j<(n-i)-1; j++)
		{
			if(arr[j] > arr[j+1])
			{
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}


int main(void)
{
	int arr[4] = {3, 2, 4, 1};
	int i;

	BubbleSort(arr, sizeof(arr)/sizeof(int));

	for(i=0; i<4; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

 

버블 정렬은 최악의 경우가 N, N-1, N-2, ..., 1의 순서로 나열되어 있는 경우인데, 이 경우 비교의 횟수는 (N-1) + (N-2) + ... 1이 되므로, 시간 복잡도는 O(N^2)이 된다.

 

2. 선택 정렬(Selection Sort)

선택 정렬은 아래의 과정을 따른다.

• N개의 데이터를 쭉 검색하여, 가장 앞서는 데이터를 가장 첫 칸으로 옮기고, 첫 칸을 고정한다.
• 나머지 N-1개의 데이터를 쭉 검색하여, 나머지에서 가장 앞서는 데이터를 둘째 칸으로 옮기고, 둘째 칸을 고정한다.
• 위 과정을 반복하여 정렬한다.

이를 위해서는, temp라는 변수를 두어 해당 sweep마다 가장 작은 변수를 저장해 놓아야 한다. 코드로는 아래와 같이 작성할 수 있다.

#include <stdio.h>

void SelSort(int arr[], int n)
{
	int i, j;
	int maxIdx;
	int temp;

	for(i=0; i<n-1; i++)
	{
		maxIdx = i;

		for(j=i+1; j<n; j++) 
		{
			if(arr[j] < arr[maxIdx])
				maxIdx = j;
		}


		temp = arr[i];
		arr[i] = arr[maxIdx];
		arr[maxIdx] = temp;
	}
}


int main(void)
{
	int arr[4] = {3, 4, 2, 1};
	int i;

	SelSort(arr, sizeof(arr)/sizeof(int));

	for(i=0; i<4; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

 

선택 정렬은 비교연산의 경우 최악의 경우는 (N-1) + (N-2) + ... +1번 해야 한다. 즉, 버블 정렬과 마찬가지로 O(N^2)인 것이다. 하지만, 선택 정렬은 버블 정렬보다 최악의 경우에서 교환 연산(이동)의 횟수가 적다.

 

반면, 버블 정렬은 최선의 경우에서 데이터 이동이 한 번도 발생하지 않는다는 장점이 있다. 따라서, 버블 정렬과 선택 정렬은 사실상 같은 수준의 알고리즘이다.

 

3. 삽입 정렬(Insertion Sort)

삽입 정렬은 배열에서 정렬이 완료된 부분과 정렬이 완료되지 않은 부분이 있을 때, 정렬이 완료되지 않은 부분의 데이터를 하나씩 정렬이 완료된 부분으로 삽입하는 알고리즘이다.

#include <stdio.h>

void InserSort(int arr[], int n)
{
	int i, j;
	int insData;

	for(i=1; i<n; i++)
	{
		insData = arr[i];

		for(j=i-1; j>=0 ; j--)
		{
			if(arr[j] > insData) 
				arr[j+1] = arr[j];
			else
				break;
		}

		arr[j+1] = insData;
	}
}


int main(void)
{
	int arr[5] = {5, 3, 2, 4, 1};
	int i;

	InserSort(arr, sizeof(arr)/sizeof(int));

	for(i=0; i<5; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

 

삽입 정렬은 대부분의 데이터가 이미 정렬되어 있을 때 특히 빠르게 작동한다. 그러나, 최악의 경우에는 앞선 두 정렬 방법과 마찬가지로 O(n^2)의 연산 복잡도를 가진다.

 

4. 힙 정렬(Heap Sort)

힙 정렬은 우선순위 큐에서 다루었던 힙을 그대로 사용한다. 즉, 우선순위를 배열 순서로 생각하면 된다. 힙은 루트 노드에 저장된 값이 가장 우선순위가 높아야 한다. 즉, 정렬의 가장 앞에 온다고 앞 수 있다.

#include <stdio.h>
#include "UsefulHeap.h"

int PriComp(int n1, int n2)
{
	return n2-n1;
//	return n1-n2;
}

void HeapSort(int arr[], int n, PriorityComp pc)
{
	Heap heap;
	int i;

	HeapInit(&heap, pc);


	for(i=0; i<n; i++)
		HInsert(&heap, arr[i]);


	for(i=0; i<n; i++)
		arr[i] = HDelete(&heap);
}

int main(void)
{
	int arr[4] = {3, 4, 2, 1};
	int i;

	HeapSort(arr, sizeof(arr)/sizeof(int), PriComp);

	for(i=0; i<4; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

 

위의 코드를 보면 알 수 있듯, 힙 정렬은 매우 간단하게 정렬되지 않은 서열을 힙에 집어넣고, 루트 노드에서 하나씩 데이터를 빼면 정렬된 서열을 얻을 수 있다. 힙 정렬은 앞선 3개의 알고리즘에 비해 훨씬 효율적인 시간 복잡도를 가지는데, 데이터를 저장하는 데 O(log_2 n), 데이터를 삭제하는 데 O(log_2 n)을 사용한다. 즉 n개의 데이터가 있으므로 힙 정렬은 O(nlogn)의 시간 복잡도를 가진다.

위 영상은 힙 정렬의 방법을 나타낸다.

 

다음 포스팅에서는 이어서 병합 정렬, 퀵 정렬, 기수 정렬을 다루고자 한다.