알고리듬 - 합병, 퀵, 기수 정렬
합병, 퀵, 기수 정렬은 앞서 알아본 버블, 선택, 삽입 정렬에 비해 구현이 어려운 대신 좋은 성능을 가지고 있다.
이에 대해 알아보자.
합병 정렬
합병 정렬(Merge Sort)은 분할 정복(Devide and Conquer)을 이용해 정렬을 하는 방식이다.
진행 과정은 아래와 같다.
1. 주어진 배열을 반으로 나눈다.
2. 왼쪽 배열과 오른쪽 배열을 각각 정렬한다.
3. 두 배열을 합쳐 하나의 정렬된 배열을 만든다.
합병 정렬은 배열을 각각 정렬할 때 재귀를 이용하는데
배열을 반으로 나누고 그 배열을 다시 반으로 나누면서 해결해야 하는 문제를 줄인다.(D&C)
먼저 전체 과정을 그림으로 보자.
합병 정렬은 분할 정복을 거쳐 정렬을 한다.
다음은 Merge 과정이다.
각 배열을 가리키는 포인터를 이용한다. 더 작은 값을 배열에 담고 1을 증가시키는 과정을 거친다.
코드는 아래와 같다.
먼저 MergeSort를 재귀하면서 모든 index에 접근할 수 있도록 한다.
void MergeSort(int arr[], int head, int tail) {
int mid = 0;
if(head < tail) {
mid = (head+tail)/2;
MergeSort(arr, head, mid); //왼쪽 정렬
MergeSort(arr, mid+1, tail); //오른쪽 정렬
Merge(arr, head, mid, tail);
}
}다음은 Merge 코드이다.
void Merge(int arr[], int head, int mid, int tail) {
int result[ARR_SIZE];
int i = head;
int j = mid+1;
for(int k = head; k <= tail; k++) {
if(i > mid)
result[k] = arr[j++];
else if(j > tail)
result[k] = arr[i++];
else if(arr[i] < arr[j])
result[k] = arr[i++];
else
result[k] = arr[j++];
}
for(i=head; i<=tail; i++){
arr[i] = result[i];
}
}
전체 코드
#include <stdio.h>
#define ARR_SIZE 9
void Merge(int arr[], int head, int mid, int tail) {
int result[ARR_SIZE];
int i = head;
int j = mid+1;
for(int k = head; k <= tail; k++) {
if(i > mid)
result[k] = arr[j++];
else if(j > tail)
result[k] = arr[i++];
else if(arr[i] < arr[j])
result[k] = arr[i++];
else
result[k] = arr[j++];
}
for(i=head; i<=tail; i++){
arr[i] = result[i];
}
}
void MergeSort(int arr[], int head, int tail) {
int mid = 0;
if(head < tail) {
mid = (head+tail)/2;
MergeSort(arr, head, mid); //왼쪽 정렬
MergeSort(arr, mid+1, tail); //오른쪽 정렬
Merge(arr, head, mid, tail);
}
}
int main() {
int arr[ARR_SIZE] = {6,1,7,2,9,4,8,3,5};
printf("정렬 전 : ");
for(int i = 0; i < ARR_SIZE; i++)
printf("%d", arr[i]);
MergeSort(arr, 0, ARR_SIZE);
printf("\n정렬 후 : ");
for(int i = 0; i < ARR_SIZE; i++)
printf("%d", arr[i]);
return 0;
}
합병 정렬의 시간 복잡도를 계산해 보자.
Merge 함수
2개의 for문이 각각 있으므로 O(n)의 시간복잡도이다.
MergeSort 함수
MergeSort함수의 시간복잡도를 T(n)이라고 할 때 MergeSort를 2번 재귀호출하므로
점화식 T(n) = 2T(n/2) + O(n).
따라서 시간복잡도는 O(n log n)이다.
퀵 정렬
퀵 정렬(Quick Sort)은 pivot(기준값)을 이용하는 정렬 방법이다.
과정은 아래와 같다.
1. 무작위 index를 선정해 pivot을 고른다.
2. pivot을 기준으로 작은 값은 앞으로, 큰 값은 뒤로 분류한다.
3. 분류한 두 배열을 각각 정렬한다.
이때 2번 과정을 Partition이라고 하고 3번 과정은 재귀를 이용한다.
그림으로 과정을 확인해 보자.
먼저 pivot은 5번 index(value: 4)로 정했다.
이후 pivot의 위치를 마지막 index와 바꾼다.
바꾸는 이유는 이후의 작업을 좀 더 편하게 하기 위함이다.
이제 포인터 i를 배열 앞부터 확인해 가면서 pivot과 비교한다.
만약 pivot보다 작은 값이 있다면 k번째 index와 swap 후 k를 증가시킨다.
위 과정을 거치면 마지막 배열의 모습이 된다.
이제 아래 그림처럼 pivot과 k번째 인덱스의 위치를 바꾼다.
그러면 pivot 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 위치하게 된다.
이제 좌 우를 각각 정렬한다. 결과는 아래 그림과 같다.
이제 코드로 확인해 보자.
QuickSort 함수
void QuickSort(int arr[], int left, int right){
if(left<right){
int randomNum = partition(arr, left, right);
QuickSort(arr, left, randomNum-1);
QuickSort(arr, randomNum+1, right);
}
}재귀만 있을 뿐 어려운 부분은 없다.
partition 함수
int partition(int arr[], int left, int right){
int pivot, tmp, l = left;
pivot = arr[left];
SWAP(arr[left], arr[right], tmp); //pivot값을 맨 뒤로 보냄
for(int i = left; i < right; i++)
if(pivot > arr[i]) {
SWAP(arr[i], arr[l], tmp);
l++;
}
SWAP(arr[right], arr[l], tmp);
return l;
}위의 이론만 이해하면 간단한 코드이다.
전체 코드
# include <stdio.h>
# define MAX_SIZE 9
# define SWAP(x, y, tmp) ( (tmp)=(x), (x)=(y), (y)=(tmp) )
int partition(int arr[], int left, int right){
int pivot, tmp, l = left;
pivot = arr[left];
SWAP(arr[left], arr[right], tmp); //pivot값을 맨 뒤로 보냄
for(int i = left; i < right; i++)
if(pivot > arr[i]) {
SWAP(arr[i], arr[l], tmp);
l++;
}
SWAP(arr[right], arr[l], tmp);
return l;
}
void QuickSort(int arr[], int left, int right){
if(left < right){
int randomNum = partition(arr, left, right);
QuickSort(arr, left, randomNum-1);
QuickSort(arr, randomNum+1, right);
}
}
void main(){
int arr[MAX_SIZE] = {6,1,7,3,9,4,8,2,5};
printf("정렬 전 : ");
for(int i=0; i < MAX_SIZE; i++)
printf("%d ", arr[i]);
QuickSort(arr,0, MAX_SIZE-1);
printf("\n정렬 후 : ");
for(int i=0; i<MAX_SIZE; i++)
printf("%d ", arr[i]);
}퀵 정렬의 시간복잡도를 계산해 보자.
partition 함수는 하나의 for문만 돌고 있으므로 O(n)이다.
QuickSort 함수는 재귀 호출을 2번 진행하는데, pivot의 값에 따라 복잡도가 달라진다.
따라서 위 코드의 점화식 T(n) = T(r - 1) + T(n - r) + O(n)이다. (r은 pivot 값)
이는 두 경우로 구분할 수 있는데,
1. r = 1이거나 r = n인 경우(즉, pivot의 값이 최소이거나 최대인 경우 - 최악의 경우)
- T(n) = T(n - 1) + O(n) = O(n2)
2. 그 외 경우의 평균
- O(n log n)
이다.
기수 정렬
기수 정렬(Radix Sort)은 다른 정렬과 다르게 값을 비교하지 않고 자릿수를 비교한다.
예를 들어 123과 456이 있다면 3과 6, 2와 5, 1과 4를 비교한다.
진행 과정은 다음과 같다.
1. 0 ~ 9까지 값을 담을 10개의 버킷(Bucket)을 준비한다.(Bucket = 큐(Queue))
2. 모든 데이터를 가장 낮은 자릿수에 맞게 버킷에 담는다.
3. 0부터 차례대로 데이터를 다시 가져온다.
4. 자릿수를 높여가며 위의 과정을 반복한다.
그림으로 과정을 확인해 보자.
먼저 10개의 버킷을 준비한 후 일의 자리에 따라 데이터를 버킷에 담는다.
이후 0번 버킷부터 차례대로 정렬한다.
이후 십의 자리에서도 동일하게 진행하면 결과는 아래와 같다.
올바르게 정렬된 것을 확인할 수 있다.
일의 자리부터 비교하므로 스택이 아닌 큐를 이용해야 결과가 올바르게 나온다.
이제 코드를 확인해 보자.
기수 정렬은 Java를 이용해 보았다.
main 함수 클래스
public class RadixSortMain {
public static void main(String[] args) {
int[] arr = {12, 27, 23, 46, 58, 96, 76, 68, 99, 30};
RadixSort rs = new RadixSort();
System.out.print("Before: ");
for(int i : arr)
System.out.print(i + " ");
System.out.println();
System.out.print("after: ");
for(int i : rs.sort(arr))
System.out.print(i + " ");
}
}
기수 정렬 클래스
import java.util.*;
class RadixSort {
private int BUCKETNUM = 10;
Queue<Integer>[] bucketArr = new LinkedList[BUCKETNUM];
int[] sort(int[] arr) {
//배열에서 가장 큰 자릿수 값을 담을 변수
int maxDigit = checkDigit(arr);
return inputBucket(arr, maxDigit);
}
//최대 자릿수 구하기
int checkDigit(int[] arr) {
int maxNum = 0;
for(int i : arr)
maxNum = Math.max(maxNum, (int)(Math.log10(i) + 1));
return maxNum;
}
int[] inputBucket(int[] arr, int num) {
//10개의 bucket 생성
for(int i = 0; i < bucketArr.length; i++)
bucketArr[i] = new LinkedList<>();
//자릿수만큼 반복
int digit = 0;
while(digit < num) {
//배열의 값들을 버킷으로 옮김
for(int i = 0; i < arr.length; i++) {
bucketArr[(arr[i] / (int)Math.pow(10, digit)) % 10].offer(arr[i]);
int k = 0;
for(int i = 0; i < bucketArr.length; i++)
while(!bucketArr[i].isEmpty())
arr[k++] = bucketArr[i].poll();
digit++;
}
return arr;
}
}기수 정렬의 시간복잡도를 구해보자.
위 코드에서 가장 중요한 부분은 inputBucket() 메서드이다.
while문 안에 for문, while문이 있긴 하지만 반복 횟수가 상수이므로
가장 중요한 부분은 digit이다.
따라서 시간복잡도는 O(kn)이다. (k는 최대 자릿수)