정렬 알고리즘

1. Bubble Sort

💡 동작원리

이 글에서는 Bubble Sort(버블정렬)에 대해 다뤄보려고 한다. Bubble Sort(버블정렬)의 원리는 가장 인접한 두 원소를 비교하여, 차순에 맞게 스왑하는 것이다.

위 그림은 오름차순으로 정렬하는 Bubble Sort(버블정렬)의 동작원리를 그림으로 표현한 것이다. i번째 원소와 i+1번째 원소를 비교하여 i번째 원소가 크면 스왑한다. 이를 끝까지 한 번 시행하면, 배열에서 가장 큰 원소가 N번째에 위치하게 된다. 이렇게 정렬되는 원소를 제외하고 계속 시행하면 배열이 오름차순으로 정렬된다. 이것이 Bubble Sort(버블정렬)이다.

💻 코드

void Bubble_Sort(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N - i; j++){
            if(Arr[j] > Arr[j + 1]){
                swap(Arr[j], Arr[j + 1]);
            }
        }
    }
}

⏱ 시간복잡도

(N-1) + (N-2) + ... + 1 = N(N-1)/2 이므로 시간복잡도는 $O(N^2)$가 된다.

$O(N^2)$

---

2. Insertion Sort

💡 동작원리

이 글에서는 Insertion Sort(삽입정렬)에 대해 다뤄보려고 한다. Insertion Sort(삽입정렬)의 원리는 인덱스가 1부터 N-1까지의 원소를 순서대로 하나씩 제 위치를 찾아서 삽입하며 정렬하는 것이다.

위 그림은 오름차순으로 정렬하는 Insertion Sort(삽입정렬)의 동작원리를 그림으로 표현한 것이다. 1번 원소부터 N-1번 원소의 위치를 찾아서 그 사이에 넣고 배열을 뒤로 미는 것을 확인할 수 있다. i번째 원소의 위치를 찾는 과정은 다음과 같다. i-1, i-2, ... 를 하나씩 탐색해, i번째 원소보다 더 크면 뒤로 한칸씩 밀고, i번째 원소보다 작은 원소가 나타나면 탐색을 멈추고 그 자리에 i번째 원소를 삽입한다. 이것이 Insertion Sort(삽입정렬)이다.

💻 코드

void Insertion_Sort(){
    for (int i = 1; i < N; i++) {
    	int temp = Arr[i];
        int j;
        for(j = i - 1; j >= 0; j--){
            if(Arr[j] > temp) Arr[j + 1] = Arr[j];
            else break;
        }
        Arr[j + 1] = temp; 
    }
}

⏱ 시간복잡도

Insertion Sort(삽입정렬)는 i번째 원소의 위치를 찾는 과정에서의 연산 횟수가 일정하지 않아서 최선의 경우와 최악의 경우로 나뉘게 된다.

먼저 최선의 경우를 살펴보자. 최선의 경우는 모두 한 번만에 i번째 원소의 위치를 찾게 되는 것이기 때문에 연산 횟수가 N-1이 된다. 따라서 시간복잡도는 $O(N)$이다.

최악의 경우를 살펴보자. 최악의 경우에는 모든 i번째 원소에 대하여 위치를 찾을 때, i-1번째 원소부터 0번째 원소를 탐색하는 것이다. 따라서 연산 횟수가 $1 + 2 + ... + N-1 = N(N-1)/2$이므로 시간복잡도는 $O(N^2)$이다.

Best case : $O(N)$
Worst case : $O(N^2)$

---

3. Selection Sort

💡 동작원리

이 글에서는 Selection Sort(선택정렬)에 대해 다뤄보려고 한다. Selection Sort(선택정렬)의 원리는 정렬되지 않은 부분배열에서 가장 큰 값, 혹은 가장 작은 값을 찾고 스왑하여 정렬하는 것이다.

위 그림은 오름차순으로 정렬하는 Selection Sort(선택정렬)의 동작원리 중 첫 단계를 그림으로 표현한 것이다. 시행의 목적은 가장 작은 값을 선택해 제일 앞으로 보내주는 것이다. 그래서 정렬되지 않은 부분배열의 가장 앞 원소를 가장 작은 값이라고 가정하고, 뒤에 값들을 비교하며 가장 앞 원소보다 작은 값이 나오면 그 값의 인덱스를 저장하는 방식으로 계속 반복한다. 배열의 끝까지 탐색했을 때, 제일 처음 시작한 원소와 가장 작은 값의 인덱스가 다르면 스왑해준다. 이 시행을 배열이 정렬 될 때까지 해준다. 이렇게 가장 큰 값, 또는 가장 작은 값을 선택하여 정렬시켜주는 방식이 Selection Sort(선택정렬)이다.

💻 코드

void Selection_Sort(){
	for(int i = 0 ; i < N; i++){
		int temp = i;          
		for(int j = i  + 1; j < N; j++)  {
			if(Arr[j] < Arr[temp]) temp = j;   
		}
		if(i != temp) swap(Arr[i], Arr[temp]);   
	}
}

⏱ 시간복잡도

연산 횟수를 계산해보면, $(N-1) + (N-2) + ... + (1) = N(N-1)/2$ 이므로 시간복잡도는 $O(N^2)$이 된다.

$O(N^2)$

---

4. Counting Sort

💡 동작원리

이 글에서는 Counting Sort(계수정렬)에 대해 다뤄보려고 한다. Counting Sort(계수정렬)의 원리는 원소값의 개수를 세고 새로운 배열에 그 갯수에 따라서 위치를 설정해주는 것이다.

새로운 배열을 선언하고, 정렬할 배열의 원소들을 계산해서 저장해준다. 새로운 배열의 이름을 Count라고 하자. Count의 인덱스 값은 정렬할 배열의 원소값이 될 것이고, Count의 데이터 값은 인덱스 값의 갯수가 될 것이다. 예를들어 정렬할 배열에 3이라는 원소가 5개가 있었다면, Count[3] = 5가 되는 것이다. 정렬할 배열을 i=0부터 i=N-1까지 한 번만 탐색하면 위 그림처럼 Count배열을 채울 수 있다.

이제 Output 배열을 선언하여 기존의 배열을 정렬한다. Output에 올바르게 정렬을 하기 위해서, Count의 값을 Count의 인덱스가 Output에 들어갈 수 있는 최대 인덱스로 바꾸어준다. 이는 Count의 값을 자신보다 앞에 있는 원소들의 합으로 바꾸어주면 된다. Count[i] = Count[i] + Count[i-1] 점화식을 이용한다.

드디어 Output 배열을 채울 수 있게 되었다. 이제는 정렬할 배열을 다시 탐색하며 Count을 참고해 Output 배열에 차곡차곡 원소를 채워넣으면 된다. Output 배열에 원소를 넣을 때마다, Count의 값은 -1을 하여 Output 배열이 완성됐을 때, Count의 값은 Count의 인덱스가 Output에 들어간 최소 인덱스로 되도록 한다. 이것이 Countring Sort(계수정렬)이다.

💻 코드

void Counting_Sort(){
	for (int i = 0; i < N; i++) Count[Arr[i]]++;
	for (int i = 1; i <= Max; i++) Count[i] = Count[i] + Count[i - 1];
	for (int i = 0; i < N; i++){
		Count[Arr[i]]--;
		Output[Count[Arr[i]]] = Arr[i];
	}
}

⏱ 시간복잡도

Countring Sort(계수정렬)의 시간복잡도는 다른 정렬과 다르게 타 원소와 비교를 하여 스왑하는 방식으로 정렬을 하는 것이 아닌, 단지 원소의 개수를 세는 것으로 자연스럽게 정렬이 되는 알고리즘이기 때문에 시간복잡도는 $O(N)$이다.

하지만, 정렬해야하는 데이터 값 중 최대값의 크기만큼의 배열을 선언해줘야하기 때문에 데이터 값의 범위가 넓을 수록 그만큼 공간복잡도가 커져서 실행속도가 늦어진다. 그렇기 때문에 Countring Sort(계수정렬)을 사용하려면 데이터 값의 범위를 반드시 확인해야한다.

$O(N)$

---

5. Quick Sort

💡 동작원리

이 글에서는 Quick Sort(퀵정렬)에 대해 다뤄보려고 한다. Quick Sort(퀵정렬)의 원리는 분할 정복 방법에 있으므로, 분할 파트와, 정복 파트를 나누어서 설명한다.

우선, 분할 파트이다. 정렬해야하는 배열을 Array라고 하자. Array에서의 아무 원소를 골라서 고른 원소를 기준으로 분할을 한다. 이때 고른 원소는 pivot(피벗)이라고 한다. Array에서 pivot보다 작은 값은 pivot의 왼쪽으로, 큰 값은 모두 오른쪽으로 보낸다. 이 과정을 partition(파티션)이라고 한다.

이제 정복 파트를 보자. 정복 파트는 위 분할 파트를 재귀적으로 호출하는 것이다. 앞 과정에서의 pivot의 위치가 q라면, Array의 첫 원소부터 q-1번째 원소까지와 q+1번째 원소부터 마지막 원소까지 다시 분할 파트를 해주는 것이다. 이를 재귀적으로 호출하며 Array를 정렬해 정복한다.

💻 코드

int Partition(int Left, int Right){
	int Pivot_Value = Arr[Left];
	int Left_Mark = Left + 1, Right_Mark = Right;
	while(Left_Mark <= Right_Mark){
		while(Arr[Left_Mark] <= Pivot_Value){ Left_Mark++; }
		while(Arr[Right_Mark] > Pivot_Value){ Right_Mark--; }
		if(Left_Mark < Right_Mark) { swap(Arr[Left_Mark],Arr[Right_Mark]); }
	}
	swap(Arr[Left], Arr[Right_Mark]);
	return Right_Mark;
}
 
void Quick_Sort(int Left, int Right){
	if (Left < Right){
		int Pivot = Partition(Left, Right);
		Quick_Sort(Left, Pivot - 1);
		Quick_Sort(Pivot + 1, Right);
	}
}

위 코드는 Quick Sort(퀵정렬)의 간단한 코드이다.

우선, Partition 함수부분부터 설명하겠다. pivot(피벗)은 항상 정복하려고 하는 부분 배열의 가장 앞을 바라보게 설정했고, Pivot_Value라고 변수명을 설정하여 pivot(피벗)의 데이터값을 저장하였다. pivot(피벗)을 기준으로 작은 값과 큰 값을 나누기 위해서는 두 개의 포인터가 필요해서 Left_Mark, Right_Mark라는 변수를 선언하여 각각 부분 배열의 두 번째 값과 제일 마지막 값을 저장해주었다. 이제 본격적으로 pivot(피벗)을 기준으로 작은 값과 큰 값을 나누어주는데 나누는 방식은 Left_Mark는 오른쪽으로 탐색하며 pivot(피벗)보다 큰 값을 찾고, Right_Mark는 왼쪽으로 탐색하며 pivot(피벗)보다 작은 값을 찾는다. 그 값을 찾게 되면, 서로 스왑해준다. 이를 Left_Mark와 Right_Mark가 만날 때까지 반복해주면 pivot(피벗)을 기준으로 작은 값과 큰 값이 분할이 된다. 마지막으로 pivot(피벗)과 Right_Mark를 스왑해주면 pivot(피벗)보다 작은 값은 앞으로, 큰 값은 뒤로 정렬되게 된다. 그리고 Partition 함수는 pivot(피벗)의 인덱스 값을 리턴해주는데, pivot(피벗)과 Right_Mark를 스왑했기 때문에 Right_Mark를 리턴해주면 된다.

이제 Quick_Sort 함수를 살펴보자. Quick_Sort함수의 제일 첫 부분은 if(Left < Right)인데 이 부분은 배열의 분할을 최소 2개 단위까지 분할 정복하기 위한 것이다. Quick_Sort 함수는 Partition 함수에 비해 비교적 간단하다. Partition 함수로부터 pivot(피벗)의 인덱스 값을 리턴받는다. pivot(피벗)을 기준으로 앞 부분배열과 뒷 부분배열을 나누어서 재귀함수를 호출하여 정복하면 된다. 아래 그림은 코드를 시각적으로 설명한다.

⏱ 시간복잡도

Quick Sort(퀵정렬)은 pivot(피벗)의 인덱스에 따라서 불균등하게 나뉘기 때문에 최선의 경우와 최악의 경우가 나뉘게 된다.

먼저 최선의 경우를 살펴보자. 최선의 경우는 pivot(피벗)이 모든 경우에 정복하려는 배열의 정중앙에 들어가는 것이다. 그렇게 되면 퀵 정렬이 한 번 호출 될 때마다 1/2로 쪼개진다. 따라서, 퀵 정렬의 재귀 호출 깊이는 $log_2N$이다. 한 호출마다 $N$번의 시행이 되기 때문에, 최선의 경우에 시간복잡도는 $O(Nlog_2N)$이다.

이번엔 최악의 경우를 살펴보자. 최악의 경우는 pivot(피벗)이 모든 경우에 정복하려는 배열의 제일 앞에 들어가는 것이다. 그렇게 되면 퀵 정렬의 재귀 호출 깊이는 $N$이 된다. 따라서 최악의 경우에 시간복잡도는 $O(N^2)$이다.

Best case : $O(Nlog_2N)$
Worst case : $O(N^2)$

---

6. Merge Sort

💡 동작원리

이 글에서는 Merge Sort(병합정렬)에 대해 다뤄보려고 한다. Merge Sort의 원리는 배열을 나누었다가, 다시 합치는 것에 있다. 따라서, 분할 정복 알고리즘이라고 할 수 있다. 다시 합치는 과정에서 정렬을 하기 때문에 Merge Sort(병합정렬)이라고 한다.

Merge Sort의 첫 단계는 배열을 크기가 1이 될 때까지 분할하는 것이다. 끝이다. 이제 다음 단계로 넘어가자.

Merge Sort의 다음 단계는 분할한 배열들을 정렬하면서 합치는 것이다. 분할된 배열들을 병합할 때는 2개씩 합친다. 분할된 배열 중 왼쪽에 있는 배열(p ~ q)의 인덱스를 가르킬 변수(Left_Index라고 하자), 오른쪽에 있는 배열(q+1 ~ r)의 인덱스를 가르킬 변수(Right_Index라고 하자), 그리고 병합되는 배열의 인덱스를 저장할 변수(Merge_Index라고 하자), 총 세 변수가 필요하다. 또한, 분할된 배열의 데이터들이 정렬된 채로 합쳐질 때, 임시로 저장할 공간이 필요하다. Left_Index에 저장된 값과 Right_Index에 저장된 값을 비교하여 작은 값을 임시 배열의 인덱스가 p인 공간에 저장한다. 그리고 저장된 변수가 다음 원소를 바라볼 수 있도록 +1해준다. 이 방법을 반복하면 두 배열을 병합하는 과정에서 오름차순으로 원소가 저장되게 된다. 만약 Left_Index 또는 Right_Index 중 하나가 분할된 배열의 끝까지 도달하게 되면, 아직 끝까지 도달하지 못한 Index는 남은 원소를 별도의 비교없이 순서대로 저장해주면 된다. 이후 임시 배열에 정렬된 범위(p ~ r)만큼 본래의 배열에 복사해준다.

💻 코드

void Merge(int Left, int Mid, int Right){
	int Left_Index = Left;
	int Right_Index = Mid + 1;
	int Merge_Index = Left;

	while(Left_Index <= Mid && Right_Index <= Right){
		if(Arr[Left_Index] <= Arr[Right_Index]) Sorted[Merge_Index++] = Arr[Left_Index++];
		else Sorted[Merge_Index++] = Arr[Right_Index++];
	}

	if(Left_Index > Mid){ for(int i = Right_Index; i <= Right; i++) Sorted[Merge_Index++] = Arr[i]; }
	else { for(int i = Left_Index; i <= Mid; i++) Sorted[Merge_Index++] = Arr[i]; }

	for(int i = Left; i <= Right; i++){ Arr[i] = Sorted[i]; }
}

void Merge_Sort(int Left, int Right){
	if(Left < Right){
		int Mid = (Left + Right)/2; 
		Merge_Sort(Left, Mid);
		Merge_Sort(Mid + 1, Right);
		Merge(Left, Mid, Right);
	}
}

위 코드는 Merge Sort(병합정렬)의 간단한 코드이다.

먼저 Merge함수에 대해 설명하겠다. 💡동작원리에서 설명했듯이, Left_Index, Right_Index, Merge_Index 세 변수를 선언해주고, 각각 왼쪽 배열의 첫 인덱스, 오른쪽 배열의 첫 인덱스, 병합될 배열의 첫 인덱스를 저장해준다. 그리고 Left_Index, Right_Index 중 하나가 자신의 범위를 넘어갔을 때 멈추는 조건으로 반복문을 만들어준다. 이때 두 Index의 값을 비교하며 오름차순에 맞게 Sorted(임시배열)에 차근차근 원소를 저장해준다. 이후 두 Index 중 아직 다 저장을 못해준 배열을 마저 저장해준다. 그리고 마지막으로 Arr(본배열)에 Sorted(임시배열)을 복사해주면 두 배열이 오름차순으로 정리된 채 저장이 된다.

다음은 Merge_Sort함수이다. 우선 조건문으로 Left < Right을 해서 배열이 1개 단위까지 쪼개졌을 때 Merge함수, 즉 병합이 되도록 해준다. 배열이 1개 단위로 쪼개는 방법은, Mid 변수를 선언하여 Merg_Sort함수를 Left부터 Mid까지, Mid+1부터 Right까지 재귀호출방식을 사용한다. 조건문에 의해 배열이 1개 단위까지 쪼개지게 될 것이고, 이후에 Merge함수가 호출되어 배열 전체가 병합된다.

⏱ 시간복잡도

Merge Sort(병합정렬)의 시간복잡도를 계산해보면 Quick Sort(퀵소트)의 이상적인 경우의 시간복잡도와 같게 된다. Merge Sort은 Quick Sort와 달리 쪼개지는 것이 항상 일정하기 때문에, 모든 경우에 시간복잡도는 같다. 따라서 Merge Sort의 시간복잡도는 $O(NlogN)$이다.

그러나 Merge Sort의 시간복잡도가 항상 $O(NlogN)$인만큼 단점도 있다. 바로 공간복잡도이다. Merge Sort는 병합하는 과정에서 임시로 저장할 배열의 할당이 필요했다. 따라서 정렬해야하는 배열의 크기만큼의 임시배열이 필요하다. Merge Sort에 필요한 공간은 Quick Sort의 두배이다.

$O(NlogN)$

---

7. Heap Sort

💡 동작원리

이 글에서는 Heap Sort(힙정렬)에 대해 다뤄보려고 한다. Heap Sort(힙정렬)의 원리는 완전이진트리(complete binary tree)에 있다. complete binary tree(완전이진트리)란, 트리의 모든 Node가 빈 공간 없이 순차적으로 채워져 있는 Tree를 말한다. 오름차순으로 정렬을 할 때는 Max Heap(최대힙), 내림차순으로 정렬을 할 때는 Min Heap(최소힙)을 이용한다. 이때, Max Heap(최대힙)과 Min Heap(최소힙)이란 complete binary tree(완전이진트리)이며, 각각 "부모의 노드값이 자식의 노드값보다 큰 꼴", "부모의 노드값이 자식의 노드값보다 작은 꼴"이다. 본인은 오름차순으로 정렬하는 Heap Sort(힙정렬)을 설명할 것이기 때문에, Max Heap(최대힙)을 사용한다.

Heap Sort(힙정렬)의 첫 번째 단계는 배열을 complete binary tree(완전이진트리)로 바라보고, 이를 Max Heap(최대힙)으로 만드는 것이다. 배열을 complete binary tree(완전이진트리)로 바라보는 방법은 따로 작성하지 않겠다. Max Heap(최대힙)으로 배열이 정리되어 있어야 뒤에 나올 Heapify 함수를 이용하여 배열을 오름차순으로 정렬할 수 있기 때문이다. Heapify 함수는 Tree내에서의 어떠한 원소가 Max Heap(최대힙)의 성질에 맞게 자기 자리를 찾아가는 과정이다. complete binary tree(완전이진트리)를 Max Heap(최대힙)으로 바꾸는 과정에서 Heapify 함수를 사용한다. 바꿔주는 과정은 원소가 배열의 1부터 N까지 있을 때, N/2번째 원소부터 1까지 Heapify 함수를 실행시켜주는 것이다. N/2번째 원소부터 실행시켜주는 이유는 complete binary tree(완전이진트리)의 특성상 N/2+1번째 원소부터는 자식노드가 없기 때문이다.

Heap Sort(힙정렬)의 두 번째 단계는 Max Heap(최대힙)의 성질과 Heapify 함수를 이용하여 배열을 오름차순으로 정렬하는 것이다. Max Heap(최대힙)의 성질에 의해서 Root Node가 모든 Node 중 가장 큰 Node일 것이다. 우리는 오름차순으로 배열을 정렬하고 있기 때문에, 이 Root Node와 N번째 원소를 스왑해준다. 그럼 배열 중 가장 큰 값이 제일 뒤로가고, Max Heap(최대힙) 상태가 깨지게 된다. 하지만 이전에 Max Heap(최대힙)상태에서 단 한 원소만 바뀐 것이기 때문에, Heapify함수를 이용해서 바뀐 Root Node를 올바른 위치로 보내주기만 하면 Max Heap(최대힙) 상태가 곧바로 돌아오게 된다. 따라서 Heapify함수를 이용해 Root Node를 올바른 위치로 보내주는데, 이때 유의해야할 점은 배열의 제일 끝에 저장된 가장 큰 값을 제외하고 1부터 N-1까지만 Heapify함수를 실행시켜야한다. 그럼 1부터 N-1까지 Max Heap(최대힙)상태가 되는데, 이때 다시 Root Node와 N-1번째 원소를 스왑해준다. 이후 다시 Heapify함수를 이용해 1부터 N-2까지 Max Heap(최대힙)을 만들어준다. 이를 계속 반복하면 배열이 오름차순으로 정렬된다.

💻 코드

void Heapify(int Cur, int N){
	int Cur_Idx = Cur;
	int Left_Child = Cur*2;
	int Right_Child = Cur*2 + 1;

	if ((Left_Child <= N) && (Arr[Left_Child] > Arr[Cur_Idx])) Cur_Idx = Left_Child;
	if ((Right_Child <= N) && (Arr[Right_Child] > Arr[Cur_Idx])) Cur_Idx = Right_Child;
     
	if (Cur_Idx != Cur){
		swap(Arr[Cur_Idx], Arr[Cur]);
		Heapify(Cur_Idx, N);
	}
}

void Heap_Sort(){
	for(int i = N/2; i >= 1; i--){ Heapify(i, N); }
	for (int i = N; i >= 2; i--){
		swap(Arr[i], Arr[1]);
		Heapify(1, i - 1);
	}
}

위 코드는 Heap Sort(힙정렬)의 간단한 코드이다.

우선 Heapify 함수에 대해 설명하겠다. Cur은 제자리를 찾아가야하는 원소의 위치이고, Cur_Idx에 다시 저장한다. Left_Child와 Right_Child는 배열을 complete binary tree(완전이진트리)의 성질을 이용하여 각각 저장해준다. 제자리를 찾아가야하는 원소 중 자신보다 더 큰 자식이 있다면 바꿔줘야한다. 이때 두 자식이 모두 자신보다 크면 두 자식 중 더 큰 자식을 저장해주어야한다. 이를 감안하여 코드가 짜여 있는데, Left_Child가 더 커서 Cur_Idx에 저장이 되었더라도, 다시 Right_Child가 더 크면 Cur_Idx에 Right_Child가 저장되게 코드가 짜여있다. 이후 Cur_Idx가 변화를 했다면, 기존의 Cur과 스왑을 하여 원소과 그 자식을 스왑해주고 Heapify함수를 재귀호출해준다.

다음은 Heap_Sort 함수이다. 첫 번째 줄의 반복문은 정렬이 되지 않은 배열을 Max Heap(최대힙)으로 바꿔주기 위한 것이다. 코드에 대한 설명은 위에서 했기 때문에 하지 않겠다. 자, 이제 배열은 Max Heap(최대힙)으로 정렬이 되었다. 이제 Max Heap의 Root Node를 제일 뒤로 보내주고 다시 Heapify함수를 호출하여 Max Heap(최대힙)을 만들고, 이를 Max Heap(최대힙)의 크기가 2가 될 때까지 반복해준다. 그럼 배열은 오름차순으로 정렬된다.

⏱ 시간복잡도

Heap Sort(힙정렬)의 시간복잡도를 계산해보자. 먼저 Heapify 함수의 시간복잡도를 계산해야한다. Heapify 함수의 시간복잡도는 최대 $logN$이다. complete binary tree(완전이진트리)의 성질에 의해 깊이가 $logN$이 되고, 최대깊이까지 재귀호출이 되었을 때 최대 시간복잡도가 나오기 때문이다.

이제 Heap Sort(힙정렬)의 시간복잡도를 계산해보자. Heap_Sort() 함수에서 Max Heap을 생성해줄 때 걸리는 시간복잡도는 Heapify함수를 N/2만큼 실행하기 때문에, $O(NlogN/2) = O(NlogN)$이 된다. 또한, 오름차순으로 정렬하는 반복문에서도 Heapify함수가 $N-1$번 실행이 되기 때문에 시간복잡도가 $O((N-1)logN) = O(NlogN)$이 된다. 따라서, Heap Sort(힙정렬)의 시간복잡도는 $O(NlogN)$이다.

$O(NlogN)$

---

8. Radix Sort

💡 동작원리

이 글에서는 Radix Sort(기수정렬)에 대해 다뤄보려고 한다. Radix Sort의 원리는 데이터의 낮은 자리수를 이용하여 정렬하는 것이다. Radix Sort는 다른 원소들과 비교 연산을 하지 않아 정렬 속도가 굉장히 빠르다. 그러나 정렬과정에 추가 메모리가 필요하다.

먼저, Radix Sort를 실행하는데에는 추가 메모리인 0 ~ 9까지의 Backet이 필요하다. 이 Backet은 Queue(큐)가 배열을 이용해 연속적으로 할당이 된 자료구조를 가지고 있다.

정렬할 데이터의 값이 {121, 1, 432, 423, 564, 44, 778, 57, 168, 92}이라고 하자. 이제 이 값들의 일의 자리 수에 맞게 Backet에 넣어보자.

위 그림처럼 된다. 이제 이것을 다시 배열에 넣으면, {121, 1, 432, 92, 423, 564, 44, 57, 778, 168}이 된다. 이번에는 십의 자리 수에 맞게 Backet에 넣어보자.

위 그림처럼 된다. 이제 이것을 다시 배열에 넣으면, {1, 121, 423, 432, 44, 564, 168, 57, 778, 92}이 된다. 이번에는 백의 자리 수에 맞게 Backet에 넣어보자.

위 그림처럼 된다. 이제 이것을 다시 배열에 넣으면, {1, 44, 57, 92, 121, 168, 423, 432, 564, 778}이 된다. 배열을 살펴보면 정렬이 끝났다. 이것이 Radix Sort이다. 배열의 데이터 중 가장 큰 자릿수만큼 위 방법을 시행해주면 배열의 모든 데이터의 정렬이 끝난다.

💻 코드

void Radix_Sort(){
	int Max_Value = 0;
	for(int i = 0; i < N; i++){ if(Max_Value < Arr[i]) Max_Value = Arr[i]; }

	int Radix;
	for(Radix = 1; Radix < Max_Value; Radix *= 10){}
	
	for (int i = 1; i <= Radix; i = i * 10){
		for (int j = 0; j < N; j++){
			int Temp = (Arr[j] / i) % 10;
			Backet[Temp].push(Arr[j]);
		}
 
		int Idx = 0;
		for (int j = 0; j < 10; j++){
			while (!Backet[j].empty()){
				Arr[Idx] = Backet[j].front();
				Backet[j].pop();
				Idx++;
			}
		}
	}
}

위 코드는 Radix Sort의 간단한 코드이다. 우선 정렬할 배열에서 가장 큰 값을 찾는다. 그리고 가장 큰 값의 자릿수를 구하여, Backet을 이용해 배열을 정렬해야하는지를 찾는다. 그리고 💡 동작원리에서 설명한 것 처럼, Backet에 자릿 수를 참고하여 넣는다. X자릿수의 값을 구하는 코드는 (원소 / X) % 10을 하면 된다(이유는 계산해보길..). 그리고 다시 Backet에서 수를 빼면서 배열에 순서대로 저장한다. 이를 최대값의 자릿수만큼 반복하여 배열을 정렬한다.

⏱ 시간복잡도

Radix Sort의 시간복잡도는 $O(dN)$이다. 빅오 표기법에 의해 $O(N)$이다. 하지만, 단점으로 Backet으로 사용할 Queue로 이루어진 배열을 선언해주어야 하기 때문에 그만큼 추가 메모리가 든다.

$O(dN) = O(N)$