C# 정렬 알고리즘 2 ( 퀵 정렬 / 병합 정렬 )
앞 포스트에 이어 정렬 알고리즘인 삽입정렬과 퀵 정렬에 대해 알아보도록 하자.
3. 퀵 정렬
퀵 정렬은 가장 대표적인 방법으로 피벗(pivot)을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬하는 방법이다.
시간 복잡도: 최악의 경우에는 O(n^2), 하지만 평균적으로는 O(n log n)
공간 복잡도: 평균적으로 O(log n), 최악의 경우 O(n) (재귀 호출에 필요한 스택 공간)
분할 정복 방법을 이용하여 정렬하는 알고리즘이다.
static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static int Partition(int[] arr, int left, int right)
{
// 기준을 오른쪽으로 잡음
// { 5, 2, 4, 6, 1, 3 };
int pivot = arr[right];
int i = left - 1;
for(int j = left; j < right; j++)
{
if (arr[j] < pivot)
{
i++;
Swap(arr, i, j);
}
}
Swap(arr, i + 1, right);
return i + 1;
}
static void QuickSort(int[] arr, int left, int right)
{
if(left < right)
{
int pivot = Partition(arr, left, right);
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}
}
static void Main(string[] args)
{
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
QuickSort(arr, 0, arr.Length - 1);
foreach(int num in arr)
{
Console.WriteLine(num);
}
}
꽤 복잡해 보이지만 하나 하나 해보도록 하자.
Swap()함수
먼저 가장 위에있는 함수 Swap()은 대표적인 Swap방식으로 사람의 경우 핸드쉐이크로 1 과 2를 교환하면 되지만, 컴퓨터의 경우 하나하나 처리해줘야 하기 때문에 공간을 하나 만들어 1을 공간에 두고 2를 받은 다음 반대편쪽에서 1을 가져가는 삼각형 방식으로 진행된다.
코드 진행
먼저 QuickSort함수에 배열과 0, 그리고 배열크기 - 1을 가져간다. 이는 배열의 가장 끝자리 수를 가져오려면 총 크기의 -1을 해야 해당 수를 가져오기 때문이다.
위 코드는 우측을 기준으로 잡고 있기 때문에 좌측 끝과 우측 끝 5 와 3 을 비교하여 우측이 크다면 아래 코드가 실행된다.
그렇다면 Partition함수로 배열과 left (현재 0), right (현재 5) 를 가지고 간다.
pivot이라는 임의의 변수에 arr[right] 인 3을 넣고, 또 다른 임의의 변수 i에는 left - 1 인 -1을 넣어둔다.
반복문에서 j = left(현재는 0), j 를 rigth의 크기만큼 반복문을 돌린다.
여기서 arr[j] 가 pivot보다 작으면 즉 5 < 3 이기 때문에 Swap하지 않고 넘어가고 그 다음 수인 배열 0인 2와 비교하여 2보다 pivot이 크기 때문에 조건이 참이되어 아래 코드가 실행된다.
아래 코드에서는 i를 증가시켜 0으로 만들고, Swap함수에 i는 0이고 j는 1을 들고가서 둘을 바꿔준다.
그러면 위 사진처럼 먼저 2와 5의 위치가 바뀌어있는것을 볼 수 있다.
이후 쭉쭉 반복문을 돌다가 arr[4]에서 걸려야한다. 왜냐하면 arr[4]는 1이고, 3보다 작기 때문에 조건에 참이 되기 때문이다.
그러면 i는 아까 한번 if문을 통과하여 증가됐기 때문에 1이 되고, j는 현재 4이기 때문에 가서 둘의 위치를 다시한번 바꿔준다.
이러면 1과 5의 위치가 바뀌어 있는것을 볼 수 있다.
이제 반복문을 다 돌았고, 마지막으로 Swap함수 한번 더 불러서 right와 i + 1 즉 배열의 2번 위치와 5번위치를 바꿔준다. 왜 이런식이 나오냐면 결국 가장 오른쪽에 있던 수인 3과 비교했을 때 3보다 작아서 왼쪽으로 간 수가 2개 이기 때문에 0번자리와 과 1번 자리는 5번 자리보다 작고 나머지는 5번자리보다 크기 때문에 바꿔줄 수 있게 되는 것이다.
그렇게 4와 3의 위치를 바꿔주면 아래와 같이 된다.
그러면 2 1 3 6 5 4 가 되는데 여기서 2 1 3 / 6 5 4 이렇게 나눠서 왼쪽 비교해서 정렬하고, 오른쪽 비교해서 정렬하는 두개의 QuickSort함수 ( QuickSort(arr, left, pivot - 1), QuickSort(arr, pivot + 1, right) ) 를 실행하면 배열이 순차적으로 정렬되게 된다.
4. 병합 정렬
병합 정렬은 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 병합하는 방법이다.
시간 복잡도: 모든 경우에 대해 O(n log n)
공간 복잡도: O(n) (정렬을 위한 임시 배열이 필요하다.)
분할 정복 방법을 이용하여 정렬하는 알고리즘이다.
static void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
static void Merge(int[] arr, int left, int mid, int right)
{
int[] temp = new int[arr.Length];
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
while (i <= mid)
{
temp[k++] = arr[i++];
}
while (j <= right)
{
temp[k++] = arr[j++];
}
for (int l = left; l <= right; l++)
{
arr[l] = temp[l];
}
}
static void Main(string[] args)
{
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
MergeSort(arr, 0, arr.Length - 1);
foreach(int num in arr)
{
Console.WriteLine(num);
}
}
병합정렬은 알기 쉽게 그림으로 보도록 하자
반으로 나눠서 한다고 했는데 계속 반으로 나누면 시작 부분과 같이 모든 수가 하나로 나뉘게 된다. 이 방식이 위 함수의
MergeSort부분이다.
이렇게 쭉 나누고 왼쪽 두 숫자부터 시작하여 비교하여 작은 수는 앞으로, 큰 수는 뒤로가 된다.
위 코드의 배열은 {5, 2, 4, 6, 1, 3} 이기 때문에 5 와 2를 먼저 비교한다.
비교한 수를 temp[]라는 배열에 그 개수만큼 순차적으로 담으면 temp[2] {2, 5} 가 된다.
이를 다시 for(int l = left; left <= right; l++) 반복문을 통해 temp[] 내에 있는 내용을 arr[]로 넘겨준다.
이를 계속 반복하여 수행해주면 배열이 오름차순으로 나열되게 된다.
어려운 내용이기에 포스팅해두고 추후에 계속 보면서 익숙해지도록 하자