[Data Structure] Chapter 10-2: 복잡하지만 효율적인 정렬 알고리즘

복잡하지만 효율적인 정렬 알고리즘에 대해 알아보자.

 

 

힙 정렬

이해와 구현

• 힙 정렬(Heap Sort): 힙 자료구조를 이용하여 정렬을 진행하는 알고리즘이다.

 

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

int PriComp(int n1, int n2)
{
    return n2-n1;   //오름차순
}

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;
}

1 2 3 4

 

• 이전 챕터에서 구현한 UsefulHeap.h의 HData의 typedef 선언을 char에서 int로 바꿔야 한다.
• 정렬 기준을 바꾸려면 PriComp의 정의를 바꿔주면 된다.

 

성능평가

• 힙의 데이터 저장, 삭제 시간 복잡도는 모두 $O(log_2n)$이므로, 이를 모두 진행한 시간복잡도는 $O(2log_2n)$이지만, 빅-오 연산에서는 $O(log_2n)$와 같다.
• 총 n개의 데이터를 삽입 및 삭제하므로 힙 정렬의 시간복잡도는 $O(nlog_2n)$과 같다.

 

chapter 10-1에서 다룬 정렬 알고리즘들에 비교하여 큰 성능 차이!

 

 

병합 정렬

이해와 구현

• 병합 정렬(Merge Sort): '분할(divide)'하여 '정복(conquer)'한 후에 '결합(combine)'하여 정렬을 진행하는 알고리즘이다.
• 1단계 분할(Divide): 해결이 용이한 단계까지 문제를 분할해 나간다.
• 2단계 정복(Conquer): 해결이 용이한 수준까지 분할된 문제를 해결한다.
• 3단계 결합(Combine): 분할해서 해결한 결과를 결합하여 마무리한다.

 

병합 정렬의 과정

 

• 코드 구현 단계에서 재귀를 이용!

 

#include <stdio.h>
#include <stdlib.h>

void MergeTwoArea(int arr[], int left, int mid, int right)
{
    int fIdx = left;
    int rIdx = mid+1;
    int i;

    int * sortArr = (int*)malloc(sizeof(int)*(right+1));
    int sIdx = left;

    while(fIdx <= mid && rIdx <= right)
    {
        if(arr[fIdx] <= arr[rIdx])
            sortArr[sIdx] = arr[fIdx++];
        else
            sortArr[sIdx] = arr[rIdx++];

        sIdx++;
    }

    if(fIdx > mid)
    {
        for(i=rIdx; i<=right; i++, sIdx++)
            sortArr[sIdx] = arr[i];
    }
    else
    {
        for(i=fIdx; i <= mid; i++, sIdx++)
            sortArr[sIdx] = arr[i];
    }

    for(i=left; i<= right; i++)
        arr[i] = sortArr[i];
    
    free(sortArr);
}

void MergeSort(int arr[], int left, int right)
{
    int mid;

    if(left < right)
    {
        mid = (left+right) / 2;

        MergeSort(arr, left, mid);
        MergeSort(arr, mid+1, right);

        MergeTwoArea(arr, left, mid, right);
    }
}

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

    MergeSort(arr, 0, sizeof(arr)/sizeof(int)-1);

    for(i=0; i<7; i++)
        printf("%d ", arr[i]);
    
    printf("\n");
    return 0;
}

1 2 3 4 5 6 7

 

병합 정렬의 초기 상태와 비교 완료 상태

 

 

성능평가

병합 정렬의 성능 평가

 

 

퀵 정렬

이해와 구현

• 퀵 정렬(Quick Sort): 피벗을 이용하여 배열을 반으로 나누는 과정을 반복하여 정렬을 진행하는 알고리즘이다.

 

퀵 정렬의 기본 형태

 

 

퀵 정렬의 과정

 

• 위 과정을 반복하여 정렬을 진행!

 

#include <stdio.h>

void Swap(int arr[], int idx1, int idx2)
{
    int temp;
    temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
}

int Partition(int arr[], int left, int right)
{
    int pivot = arr[left];
    int low = left+1;
    int high = right;

    while(low <= high)
    {
        while(pivot >= arr[low] && low <= right)    
            low++;

        while(pivot <= arr[high] && high >= (left+1))
            high--;
/*
low <= right로 설정해두면 low가 배열의 정렬 범위를 넘어서지만 low는 마지막 Swap 과정에 포함되지 않기 때문에 괜찮다.
하지만, 더 깔끔하게 low가 배열 범위에서 벗어나지 않고, high가 pivot과 겹치지 않게 하기 위해서는 
두 범위를 low < right과 high > left+1로 설정하는 것이 더 깔끔할 것으로 예상된다.
*/

        if(low <= high)
            Swap(arr, low, high);
    }

    Swap(arr, left, high);
    return high;
}

void QuickSort(int arr[], int left, int right)
{
    if(left <= right)
    {
        int mid = Partition(arr, left, right);
        QuickSort(arr, left, mid - 1);
        QuickSort(arr, mid + 1, right);
    }


}

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

    int len = sizeof(arr)/sizeof(int);
    int i;

    QuickSort(arr, 0, len-1);

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

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

주석에 대한 설명

 

1 2 3 4 5 6 7

 

• 피벗을 선정할 때, 정렬 대상에서 세 개의 데이터를 추출하여 그 중간 값에 해당하는 것을 선택하는 방식으로 퀵 정렬을 진행하면 성능이 더 좋아진다.

 

성능평가

• 최악의 상황에서의 빅-오는 $O(n^2)$이다.
• 위에서 언급한 중간값을 선택하는 방법을 적용하면 퀵 정렬의 빅-오는 다음과 같이 $O(nlog_2n)$

퀵 정렬의 성능 평가

 

중간값을 찾는 퀵 정렬

#include <stdio.h>

void Swap(int arr[], int idx1, int idx2)
{
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}	

int MedianOfThree(int arr[], int left, int right)
{
	int samples[3] = {left, (left+right)/2, right};

	if(arr[samples[0]] > arr[samples[1]])
		Swap(samples, 0, 1);

	if(arr[samples[1]] > arr[samples[2]])
		Swap(samples, 1, 2);

	if(arr[samples[0]] > arr[samples[1]])
		Swap(samples, 0, 1);

	return samples[1];
}

int Partition(int arr[], int left, int right)
{
	int pIdx = MedianOfThree(arr, left, right);   // 피벗을 선택!
	int pivot = arr[pIdx];

	int low = left+1;
	int high = right;

	Swap(arr, left, pIdx);    // 피벗을 가장 왼쪽으로 이동

	printf("피벗: %d \n", pivot);

	while(low <= high)    // 교차되지 않을 때까지 반복
	{	
		while(pivot >= arr[low] && low <= right)
			low++;

		while(pivot <= arr[high] && high >= (left+1))
			high--;

		if(low <= high)    // 교차되지 않은 상태라면 Swap 실행
			Swap(arr, low, high);    // low와 high가 가리키는 대상 교환
	}

	Swap(arr, left, high);    // 피벗과 high가 가리키는 대상 교환
	return high;    // 옮겨진 피벗의 위치 정보 반환
}

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);    // 오른쪽 영역을 정렬
	}
}

int main(void)
{
	int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};

	int len = sizeof(arr) / sizeof(int);
	int i;

	QuickSort(arr, 0, sizeof(arr)/sizeof(int)-1);

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

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

피벗: 8 
피벗: 4
피벗: 2
피벗: 6
피벗: 12
피벗: 10
피벗: 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

 

 

기수 정렬

기수 정렬의 이해

• 기수 정렬(Radix Sort): 데이터를 구성하는 기본요소인 '기수(radix)'를 이용하여 정렬을 진행하는 알고리즘이다.
• 다른 일반적인 정렬 알고리즘과 달리 비교연산을 필요로 하지 않는다.
• 그러나, 기수 정렬은 적용할 수 있는 범위가 제한적이다.

 

기수 정렬의 과정

 

• 기수(radix): 데이터를 구성하는 기본 요소를 의미하며, 10진수에서는 0~9의 숫자가 기수이다.
• 버킷(bucket): 기수의 수에 해당하는 만큼 버킷을 활용한다.

 

LSD vs. MSD

• LSD(Least Significant Digit) 기수 정렬: 가장 작은 자릿수부터 시작하여 정렬을 진행하는 알고리즘이다.
• MSD(Most Significant Digit) 기수 정렬: 가장 큰 자릿수부터 시작하여 정렬을 진행하는 알고리즘이다.
• MSD 기수 정렬의 경우에는, 중간중간에 정렬이 완료된 데이터가 있는지 점검하고 ,해당 데이터를 정렬 과정에서 실시간으로 제외해야 한다.
• 중간에 정렬이 완료될 수 있는 성능적 이점을 기대할 수 있지만, 모든 데이터에 일괄적인 과정을 적용할 수 없고 구현이 어렵다는 단점으로 기수 정렬에서는 LSD가 보편적으로 사용된다.

 

LSD 기수 정렬의 과정

 

중간점검의 과정이 생략된 MSD

 

LSD 기수 정렬의 구현

• 이전 챕터에서 구현한 ListBaseQueue 자료구조를 버킷으로 이용한다.

 

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

#define BUCKET_NUM      10

void RadixSort(int arr[], int num, int maxLen)
{
    Queue buckets[BUCKET_NUM];
    int bi;
    int pos;
    int di;
    int divfac = 1;
    int radix;

    for(bi=0; bi<BUCKET_NUM; bi++)
        QueueInit(&buckets[bi]);

    for(pos=0; pos<maxLen; pos++)       //가장 긴 데이터의 길이만큼 반복
    {
        for(di=0; di<num; di++)         //정렬대상의 수만큼 반복
        {
            radix = (arr[di]/divfac % 10);

            Enqueue(&buckets[radix], arr[di]);  //버킷에 데이터 저장
        }

        for(bi=0, di=0; bi<BUCKET_NUM; bi++)
        {
            while(!QIsEmpty(&buckets[bi]))
                arr[di++] = Dequeue(&buckets[bi]);
        }

        divfac *= 10;
    }
}

int main(void)
{
    int arr[7] = {13, 212, 14, 7141, 10987, 6, 15};

    int len = sizeof(arr)/sizeof(int);
    int i;

    RadixSort(arr, len, 5);

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

    return 0;
}

6 13 14 15 212 7141 10987

 

 

성능평가

 

기수 정렬의 성능 평가

 

 

---

• 윤성우, <윤성우의 열혈 자료구조>, 오렌지미디어, 2022.04.11