Chapter 10. 정렬(Sorting)

김민정·2024년 11월 21일

c언어 sorting 개발 기술블로그 정렬 코딩

윤성우 열혈 자료구조

목록 보기

10/14

10-1. 단순한 정렬 알고리즘

이번 Chapter에서는 각종 정렬 알고리즘에 대해 알아보자.
각각의 알고리즘이 갖는 특징에 중점을 두고 알아보자.

(1) 버블 정렬 (Bubble Sort)

1) 이해와 구현

버블 정렬은 정렬의 대명사로 알려져 있는, 이미 알고 있을 수 있는 정렬 방법이다.
그만큼 이해하기도, 구현하기도 쉽다. 이해와 구현이 쉬운 만큼 성능에 아쉬움이 있다.
버블 정렬의 이해를 위해 예시로 3, 2, 4, 1이 순서대로 저장된 다음 배열을 '오름차순'으로 정렬하는 과정을 살펴보자.

버블 정렬은 인접한 두 개의 데이터를 비교해가며 정렬을 진행하는 방식이다.
두 데이터를 비교하여 정렬순서상 위치가 바뀌어야 하는 경우 두 데이터의 위치를 바꿔나간다.

No.	Pic.	Expl.
1		정렬의 우선순위가 가장 낮은, 제일 큰 값(4)을 맨 뒤로 보내기.
2		두 번째로 큰 값(3)을 맨 뒤에서 한 칸 앞으로 보내기. 정렬이 완료된(배열의 끝에 위치한) 데이터를 제외하고 나머지를 대상으로 비교와 교환 진행.
3		남은 두 데이터를 비교하고 교환하여 정렬이 완료.

버블 정렬이란 이름이 붙게 된 이유는 앞에서부터 순서대로 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 붙여진 이름이다.

다음은 버블 정렬의 구현 예시다.

#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-1); j++)
        if(arr[j] > arr[j+1])
        {
            // 데이터 교환
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
}

int main()
{
    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;
}

> 출력
1 2 3 4

위 코드에서는 버블 정렬을 구성하는 두 for문의 반복조건이 핵심이다.
따라서 바깥쪽 for문의 반복 조건과 안쪽 for문의 반복조건에 대한 정확한 이해가 필요하다.

2) 성능 평가

정렬 알고리즘의 성능은 다음 두 가지를 근거로 판단하는 것이 일반적이다.

비교의 횟수: 두 데이터간의 비교연산의 횟수
이동의 횟수: 위치의 변경을 위한 데이터의 이동횟수

'비교연산'과 데이터 이동을 위한 '대입연산'이 정렬과정의 핵심연산이기 때문이다.

실제도로 시간복잡도에 대한 빅-오를 결정하는 기준은 '비교의 횟수'다.
하지만 '이동의 횟수'까지 살펴보면 동일한 빅-오의 복잡도를 갖는 알고리즘 간의 세밀한 비교가 가능하다.

버블 정렬의 비교횟수는 다음 반복문 안에 위치한 if문의 실행 횟수를 기준으로 계산할 수 있다.
버블 정렬에서 데이터의 수가 $n$ 개일 때 진행이 되는 비교의 횟수는 다음과 같다.

그리고 이는 등차수열의 합이므로 다음과 같이 정리된다.

따라서 버블 정렬의 비교연산에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 최고 차항을 따라 $O(n^2)$ 가 된다.

단순히 반복문이 중첩되어 있을 뿐인데 실제 활용하기 부담스러운 정도의 성능을 보인다.
그렇다면 데이터의 이동횟수(교환횟수)는 어떨까?
이는 최선의 경우와 최악의 경우가 구분된다.
데이터가 이미 정렬되어 있는 상태라면 데이터의 이동(교환)이 한 번도 일어나지 않지만,
반대로 정렬기준의 역순으로 저장된 상태라면 비교의 횟수와 이동의 횟수(교환의 횟수)가 일치하기 때문이다.
따라서 데이터 이동연산에 대한 빅-오는 최악의 경우 $O(n^2)$ 가 된다.
실제로 최악의 경우 버블 정렬의 데이터 이동횟수는 비교횟수보다 3배 많아지게 된다. 값의 교환 과정에서 대입 연산이 3회 진행되기 때문이다.
하지만 빅-오를 판단하는 과정에서 계수가 생략되기 때문에 이를 무시한다.

(2) 선택 정렬 (Selection Sort)

이번에 배울 선택 정렬은 버블 정렬보다도 쉽고 간단한 알고리즘이다.

1) 이해와 구현

다음 그림과 같이 1, 2, 4, 3이 나란히 저장된 배열의 오름차순 정렬과정을 살펴보자.
간단하다는 것을 바로 알 수 있게 된다.

.	Pic.	Expl.
초기		선택 정렬은 정렬순서에 맞게 하나씩 선택해서 옮기고, 옮기면서 정렬이 되게 하는 알고리즘. 이 방법대로라면 선택 정렬은 정렬결과를 담을 별도의 메모리 공간이 필요. 하지만 데이터를 하나 옮길 때마다 공간이 하나씩 비게 된다는 사실을 기반으로 개선하게 되면 별도의 공간을 마련할 필요 없음.
개선		어떻게 보면 교환해서 정렬을 시킨다고 생각할 수 있지만 "정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈 자리에 가져다 놓는다." 라고 이해. (이게 교환 아닌가...? ㅎ) 빈자리를 활용하는 과정에서 비롯한 교환이라는 점을 이해할 필요 있다.

위에서 설명한 개선된 선택 정렬을 구현해보면 아래와 같다.

#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()
{
    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;
}

> 출력
1 2 3 4

2) 성능 평가

선택 정렬의 코드만 봤을 때는 for문이 이중으로 되어 있어 버블 정렬과 성능상 큰 차이가 없음을 알 수 있다.
그럼 비교횟수의 확인을 위해서 반복문을 좀 더 자세히 살펴보자.

바깥쪽 for문의 $i$ 가 $0$ 일 때 안쪽 for문의 $j$ 는 $1$ 부터 $n-1$ 까지 증가하여 성태 ㄱ정렬의 비교 연산은 $n-1$ 회 진행된다.
그리고 바깥쪽 for문의 $i$ 가 $1$ 일 때는 안쪽 for문의 $j$ 가 $2$ 부터 $n-1$ 까지 증가하여 선택 정렬의 비교연산은 $n-2$ 회 진행된다.
이는 버블 정렬의 경우와 똑같기 때문에 선택 정렬의 빅-오 역시 최악의 경우와 최선의 경우 구분 없이 최고 차항을 따라 $O(n^2)$ 가 된다.

언뜻보면 버블 정렬보다 나은 성능을 보장할 것처럼 보였지만 비교횟수를 기준으로 보면 차이가 없음을 알 수 있다.
그렇다면 데이터의 이동횟수도 버블 정렬과 차이가 없을까?
여기서는 제법 차이가 있다.

버블정렬이나 선택 정렬이나 데이터의 교환을 위한 세 번의 대입연산이 temp = A; A = B; B = temp;형식으로 진행된다.
하지만 이 교환이 위치하는 곳이 다르다.
버블 정렬의 경우에는 안쪽 for문에 위치해 있고,
선택 정렬의 경우 바깥쪽 for문에 위치해 있다.
때문에 선택 정렬의 경우 $n-1$ 회의 교환이 이뤄지므로 데이터의 이동횟수는 이의 세 배인 $3(n-1)$ 이 된다.
따라서 선택 정렬의 데이터 이동연산에 대한(대입연산에 대한) 빅-오는 최악의 경우와 최선의 경우 상관없이 $O(n)$ 이 된다.

최악의 경우 버블 정렬보다 선택 정렬에 좋은 성능을 기대할 수 있지만,
버블 정렬은 최선의 경우 단 한번의 데이터 이동도 발생하지 않는 점,
실제로 데이터들이 늘 최악의 상황으로 배치되지 않는다는 점을 감안하면
이 둘의 성능을 비교하는 것은 약간 무의미하다고 할 수 있다.

(3) 삽입 정렬 (Insertion Sort)

이번에 배울 삽입 정렬은 보는 관점에 따라서 별도의 메모리를 필요로 하지 않는 '개선된 선택 정렬'과 유사하다고 생각할 수 있다.
하지만 전혀 다른 방법으로 정렬을 이뤄나간다.

1) 이해와 구현

위 그림과 같은 배열이 있다고 예시를 들어보자.
배열은 정령이 완료된 부분과 완료되지 않는 부분으로 나눠있다.
삽입 정렬은 정렬 대상을 이렇게 두 부분으로 나눠서 정렬이 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 삽입해 가면서 정렬을 진행하는 알고리즘이다.
그럼 다음 그림을 통해서 5, 3, 2, 4, 1의 오름차순 정렬과정을 살펴보자.

.	Pic.	Expl.
이해		첫 번째 데이터와 두 번째 데이터를 비교하여 정렬된 상태가 되도록 두 번째 데이터를 옮기면서 정렬 시작. 첫 번째 데이터와 두 번째 데이터가 정렬이 완료된 영역 형성. 세 번째 데이터와 정렬된 부분을 비교하여 세 번째 데이터 이동. 세 번째 데이터와 네 번째 데이터가 정렬이 완료된 영역으로 삽입. 이렇게 정렬이 진행되기 위해서는 정렬된 상태로 삽입하기 위해 특정위치를 비워야하고 비우기 위해서 데이터들을 한 칸씩 뒤로 미는 연산을 수행할 필요 있음. 정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬대상이 됨. 삽입할 위치를 발견하고 데이터를 한 칸 씩 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾을 수도 있음.
구현		위에서 얘기한 '데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾는 것'을 의미하는 바를 왼쪽에서 그림으로 나타냄. 숫자 3을 정렬이 완료된 영역으로 옮기는 과정. 삽입위치를 찾는 과정과 삽입을 위한 공간마련의 과정을 구분할 필요 없음. 정렬된 영역에서 삽입의 위치를 찾는 것이니 삽입위치를 찾으면서 삽입을 위한 공간의 마련을 병행.

위에서 설명한 구현 부분을 코드로 나타내면 다음과 같다.

#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()
{
    int arr[] = {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;
}

> 출력
1 2 3 4 5

2) 성능 평가

삽입 정렬은 정렬대상의 대부분이 이미 정렬되어 있는 경우 매우 빠르게 동작한다.
삽입 정렬의 성능평가를 위해 반복문을 살펴보자.
정렬대상이 완전히 정렬된 상태라면, 안쪽 for문의 if...else문의 조건은 항상 거짓이 되어 break문을 실행해 빠져나오게 된다.
따라서 데이터의 이동도 발생하지 않고 if...else문의 조건비교도 바깥쪽 for문의 반복횟수 이상 진행되지 않는다.

하지만 최악의 경우를 생각하면, 앞에서 배운 버블 정렬 & 선택 정렬과 동일하다.
최악의 경우 안쪽 for문의 if...else문의 조건은 항상 참이 디어 break문을 한번도 실행하지 않게된다.
따라서 바깥쪽 for문의 반복횟수와 안쪽 for문의 반복횟수를 곱한 수만큼 비교연산도, 이동연산도 진행되므로
최악의 경우 비교연산과 이동연산에 대한 빅-오는 $O(n^2)$ 가 된다.

10-2. 복잡하지만 효율적인 정렬 알고리즘

앞서 배운 단순한 정렬 알고리즘들은 정렬대상의 수가 적은 경우 효율적으로 사용할 수 있어서 나름의 의미를 지닌다.
하지만 정렬대상의 수가 적지 않은 경우에는 보다 효율적인 알고리즘이 필요하다.
이번에 배울 알고리즘들이 그렇다.
소제목에서 '복잡하다'라는 단어 때문에 어려운 알고리즘일거라고 생각할 수 있지만,
앞에서 배운 알고리즘들보다 상대적으로 복잡하기 때문이지 어려운 것은 아닐 수 있다.
(오히려 기발한 정렬방식에 흥미를 느낄 수도...?😉)

(1) 힙 정렬 (Heap Sort)

힙 정렬(heap sort)은 힙을 이용한 정렬방식으로 "힙의 루트 노드에 저장된 값이 가장 커야한다."는 힙의 특성을 활용해서 정렬하는 알고리즘이다.
물론 이는 '최대 힙(max heap)'의 특징이다.
하지만, "힙의 루트 노드에 저장된 값이 정렬순서상 가장 앞선다"는 특징을 갖도록 힙을 구성할 수도 있다.

1) 이해와 구현

예제를 하나 볼 건데 이 예제만 이해하더라도 힙 정렬을 쉽게 이해할 수 있다.
이 예제를 실행하기 위해서는 앞서 공부한 Chapter 09에서 사용한 UsefulHeap.h 파일과 UsefulHeap.c 파일이 필요하다.

UsefulHeap.h : 사용 가능 수준의 힙이라 이름 붙였던 힙의 헤더파일
UsefulHeap.c : 사용 가능 수준의 힙이라 이름 붙였던 힙의 소스파일

그리고 컴파일 하기 전 UsefulHeap.h에서 typedef 선언을 typedef char HData; → typedef int HData;로 변경해야 한다.
(우리는 정수 데이터만 다룰 것이기 때문에)

#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()
{
    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;
}

> gcc .\HeapSort.c .\UsefulHeap.c
> .\a.exe
> 출력
1 2 3 4

힙 정렬의 원리를 설명하기 위해 힙 정렬을 구현한 함수의 일부를 보자.

void HeapSort(int arr[], int n, PriorityComp pc)
{
    ....
    // 힙 정렬 단계 1: 데이터를 모두 힙에 넣기.
    for(i=0; i<n; i++)
        HInsert(&heap, arr[i]);
    
    // 힙 정렬 단계 2: 힙에서 다시 데이터를 꺼내기.
    for(i=0; i<n; i++)
        arr[i] = HDelete(&heap);
}

정렬의 대상인 데이터들을 힙에 넣었다가 꺼내는 것이 전부다.
그럼에도 정렬이 완료되는 이유는 꺼낼 때 힙의 루트 노드에 저장된 데이터가 반환되기 때문이다.
위 예제는 오름차순으로 정렬하기 위해 PriComp 조건이 n2-n1으로 되어있고
이를 내림차순으로 정렬하기 위해서는 조건을 n1-n2로 변경해주면 된다.

2) 성능 평가

언뜻 보면 저장된 데이터를 한번에 힙에 넣었다가 다시 꺼내기 때문에 성능상 이점이 별로 없어 보이지만, 힙 정렬은 지금까지 소개한 정렬들 중 가장 좋은 성능을 보이는 알고리즘이다.
Chapter 09에서 비교연산의 횟수를 근거로 하여 힙의 데이터 저장 및 삭제의 시간 복잡도를 다음과 같이 정리했었다.

힙의 데이터 저장 시간 복잡도 : $O(log_2n)$
힙의 데이터 삭제 시간 복잡도 : $O(log_2n)$

따라서 삽입과 삭제를 하나의 연산으로 묶는다면 이 연산에 대한 시간 복잡도는 $O(2log_2n)$ 가 되고 2는 빅-오에서 무시할만한 크기기 때문에 $O(log_2n)$ 가 된다.
정렬과정에 대한 시간 복잡도는 정렬대상의 수가 $n$ 개라면 총 $n$ 개의 데이터를 삽입 및 삭제해야하므로 위 빅-오에 $n$ 을 곱한 $O(nlog_2n)$ 이 된다.

딱 보기엔 $O(nlog_2n)$ 이나 $O(n^2)$ 의 차이를 모를 수 있다.

위 표를 보면 $O(nlog_2n)$ 과 $O(n^2)$ 의 차이가 크다는 것을 알고 있다.
$O(n^2)$ 성능을 보이는 알고리즘을 $O(nlog_2n)$ 의 성능을 보일 수 있도록 개선한다면 이는 낮은 성능으로 인해 현실적으로 활용하기 어려운 알고리즘에서 활용이 가능한 수준으로 평가 받을 수 있다.

(2) 병합 정렬 (Merge Sort)

병합 정렬(merge sort)은 '분할 정복(divide and conquer)'이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법이다.

분할 정복이란, 말 그래도 복잡한 문제를 복잡하지 않은 문제로 '분할(divide)'하여 '정복(conquer)'하는 방법이다.
단 분할해서 정복했으니 정복한 후에는 '결합(combine)'의 과정을 거쳐야 한다.
즉, 다음 3단계를 거치도록 알고리즘을 디자인 하는 것이 분할 정복법이다.

1단계 [분할(Divide)]: 해결이 용이한 단계까지 문제를 분할해 나간다.
2단계 [정복(Conquer)]: 해결이 용이한 수준까지 분할된 문제를 해결한다.
3단계 [결합(Combine)]: 분할해서 해결한 결과를 결합하여 마무리한다.

1) 이해와 구현

위 분할 정복 방법을 근거로 병합 정렬 알고리즘의 기본 원리는 다음과 같다.
8개의 데이터를 동시에 정렬하는 것보다, 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 쉽고, 또 이들 각각을 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉬운 것이다.

따라서 병합 정렬의 방식은 다음과 같이 설명할 수 있다.

.	Pic.	Expl.
기본 원리		오른차순 정렬을 기준으로 병합 정렬의 기본 원리. 8개의 데이터를 둘씩 나눈 것이 전부지만 실제로는 훨씬 더 작게 분할. 2개의 데이터만 남을 때 까지 분할 하면, if문 하나로 간단히 정렬할 수 있기 때문. 하지만 여기서 한번 더 나눠 병합 정렬 데이터가 1개만 남을 때 까지 분할한다면 if문으로 정렬할 필요도 없기 때문에 1개만 남을 때까지 분할. 언뜻보면 병합 정렬은 나누는 것이 핵심같아 보이지만, 나눈 것을 병합하는 과정에서 그 진가가 발휘.
병합 정렬 예시		1. 분할 과정. 전체 데이터를 둘로 나누는 과정을 데이터가 하나씩 구분 될 때까지 진행. (8개의 데이터이므로 총 3회 진행) 분할 시 정렬을 고려하지 않고 그저 분할만 진행. 2. 분할이 완료되면 병합 진행. 정렬순서를 고려해서 둘을 하나로 병합. 정렬순서를 고려해서 묶기. (분할과 동일하게 총 3회 진행) 분할의 과정에서 하나씩 구분될 때까지 둘로 나누는 과정을 한 이유는 재귀적 구현을 위한 것.
병합 정렬 구현		<병합 정렬 진행하는 함수 - MergeSort> 첫 번째 인자로 정렬대상이 담긴 배열의 주소 값 전달. 두 번째 인자와 세 번째 인자로 정렬대상의 범위정보를 인덱스 값의 형태로 전달. ex.정렬대상이 배열 전체라면 배열의 첫 번째 요소와 마지막 요소의 인덱스 값을, 두 번째 인자와 세 번째 인자로 각각 전달. 병합 정렬의 경우 정렬될 데이터 갯수 정보를 전달했던 이전의 정렬 함수들과 달리 정렬의 범위정보를 전달. 마지막 문장 'MergeTwoArea'함수는 정렬된 두 영역을 하나로 묶기 위한 함수. 배열 arr의 left ~ mid까지, 그리고 mid+1 ~ right까지 각각 정렬되어 있으니 이를 하나의 정렬된 상태로 묶어서 배열 arr에 저장.

위에서 이해한 원리, 정렬을 실제 코드로 구현하면 다음과 같다.

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

    // 병합 한 결과를 담을 배열 sortArr 동적 할당
    int * sortArr = (int*)malloc(sizeof(int)*(right+1));
    int sIdx = left;

    while(fIdx<=mid && rIdx<=right) // 분할한 영역일 경우
    {
        // 병합 할 두 영역의 데이터들을 비교하여 정렬 순서대로 sortArr에 하나씩 옮기기
        if(arr[fIdx] <= arr[rIdx])  
            sortArr[sIdx] = arr[fIdx++];
        else
            sortArr[sIdx] = arr[rIdx++];

        sIdx++;
    }

    if(fIdx > mid)  // 배열의 앞부분이 모두 sortArr에 옮겨졌다면
        // 배열의 뒷부분에 남은 데이터들을 sortArr에 그대로 옮기기
        for(i=rIdx; i <= right; i++, sIdx++)
            sortArr[sIdx] = arr[i];
    else    // 배열의 뒷부분이 모두 sortArr에 옮겨졌다면
        // 배열 앞부분에 남은 데이터들 sortArr에 그대로 옮기기
        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()
{
    int arr[7] = {3, 2, 4, 1, 7, 6, 5};
    int i;

    // 배열 arr의 전체 영역 정렬
    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

여기서 MergeTwoArea 함수 안에서 while문 안에 sIdx++;를 빼먹지 않도록 주의한다.⭐
MergeTwoArea 함수의 구현이 쉽지가 않을 것이다.
그래서 이 함수의 정의에 대해서 더 자세히 이해해보자.

먼저, 위 함수에 삽입된 while문의 반복조건을 이해해야한다.
fIdx와 rIdx에는 각각 병합할 두 영역의 첫 번째 위치정보가 담긴다. (물론 위치정보는 인덱스 값이다.)
그리고 이 두 변수의 값을 증가시켜 가면서 두 영역의 데이터들을 비교해 나가게 된다.
병합할 두 영역은 하나의 배열 안에 함께 존재한다.
따라서 fIdx는 배열의 앞쪽 영역을 가리키게 되고, rIdx는 배열의 뒤쪽 영역을 가리키게 되는데 배열의 앞과 뒤를 구분하는 기준은 변수 mid에 저장되어 있다.
mid+1의 위치서부터 뒤쪽 영역이 시작되기 때문이다.

위 그림은 두 영역을 합치기 직전의 상태를 보여준다.
fIdx와 rIdx가 가리키는 위치에 저장된 값은 하나씩 증가하면서 다음과 같이 비교를 진행하게 된다.

2와 1 비교: 비교연산 후, 1을 sortArr로 이동, 그리고 rIdx값 1 증가
2와 4 비교: 비교연산 후, 2를 sortArr로 이동, 그리고 fIdx값 1 증가
3과 4 비교: 비교연산 후, 3을 sortArr로 이동, 그리고 fIdx값 1 증가
7과 4 비교: 비교연산 후, 4를 sortArr로 이동, 그리고 fIdx값 1 증가
7과 5 비교: 비교연산 후, 5를 sortArr로 이동, 그리고 fIdx값 1 증가
7과 6 비교: 비교연산 후, 6를 sortArr로 이동, 그리고 fIdx값 1 증가

이렇게 마지막 비교가 끝나게 되면 rIdx는 right를 넘어서는 위치를 가리키게 되어 더 이상 비교가 무의미해진다.
두 영역을 비교하다 보면, 한 영역의 데이터들이 모두 옮겨져서 더 이상 비교가 불가느한 상황에 도달하는데 이때 while문의 반복조건(fIdx<=mid && rIdx<=right)에서 벗어나게 되어 while문을 빠져나올 수 있게 되는 것이다.

while문을 빠져나온 뒤 어느 영역의 데이터가 남아 있는지 확인해서 그 남은 데이터를 나머지 배열에 옮기는 것으로 마무리된다. (if~else문)

2) 성능 평가

병합 정렬의 성능평가를 위해서 비교연산의 횟수와 이동연산(대입연산)의 횟수를 계산해보자.
그런데 병합 정렬의 성능은 MergeSort 함수가 아닌 MergeTwoArea 함수를 기준으로 계산해야한다.

비교연산의 횟수를 위해 while문을 살펴보자.
정렬의 우선순위를 비교하는 비교연산이 중심이므로 if(arr[fIdx] <= arr[rIdx])문장의 비교연산을 중심으로 비교연산의 횟수를 계산하면 된다.

위 그림에서 하나와 하나가 모여서 둘이 될 때 비교연산은 최대 2회 진행이 된다.
8과 2를 비교해서 하나로 뭉치게 하려면 8과 2를 비교해야하는데 이는 비교연산 횟수가 1회다.
하지만 while문 이후에 등장하는 if~else문에서의 비교연산 횟수를 포함해서 2회가 된다.
(사실 2든 1이든 빅-오를 구하는데 있어서 그 결과에 큰 영향을 끼치지 않는다.)

그렇다면 둘과 둘이 모여서 넷이 될 때, 최대 비교연산의 횟수는 어떻게 될까?
이 상황에서 최대(최악의 경우) 비교연산의 횟수는 4다.
오른쪽 분리된 배열을 예시로 들면 다음과 같이 비교가 진행된다.

1과 4 대상으로 비교연산 후 1을 sortArr로 이동
5와 4 대상으로 비교연산 후 4를 sortArr로 이동
5와 6 대상으로 비교연산 후 5를 sortArr로 이동
마지막 남은 6을 sortArr로 이동하기 위한 if~else문에서 비교연산

따라서 병합 2단계에서 8개의 데이터가 있는 배열의 비교연산 횟수는 8회가 될 것이다.
이는 정렬의 대상인 데이터의 수가 $n$ 개 일 때, 각 병합의 단계마다 최대 $n$ 번의 비교연산이 진행되고 $nlog_2n$ 으로 나타낼 수 있다.
따라서 병합 정렬의 비교연산에 대한 빅-오는 $O(nlog_2n)$ 가 된다.

이번에는 이동연산 횟수를 계산해보자.
이동연산 관점에서 MergeTwoArea 함수를 정리하면

정리된 배열을 위한 임시 배열 생성. 이 영역에 병합 결과를 정렬하여 저장 (malloc 부분)
배열 sortArr에 데이터를 정렬하며 이동 (while문)
매열 sortArr에 나머지 데이터 이동 (if~else문)
임시 배열에 저장된 데이터 전부 이동 (for문)

따라서 데이터의 이동이 발생하는 이유는 1. 임시 배열에 데이터를 병합하는 과정에서 한번
2. 임시 배열에 저장된 데이터 전부를 원위치로 옮기는 과정에서 한번
이렇게 두 가지로 볼 수 있다.

따라서 각각의 상황에서 비교연산 횟수의 2배에 해당하는 이동연산이 이뤄진다 할 수 있다.
따라서 병합 정렬의 이동연산 횟수는 최악, 평균, 최선의 경우 상관없이 $2nlog_2n$ 가 된다.
빅-오 표기에서 2는 무시할 수 있는 숫자이므로 이동연산의 빅-오는 $O(nlog_2n)$ 가 된다.

참고로 병합 정렬에는 임시 메모리가 필요하다는 단점이 있다. (sortArr를 위한)
하지만 이는 정렬의 대상이 배열이 아닌 연결 리스트의 경우 단점이 되지 않기 때문에 연결 리스트의 경우에는 병합 정렬의 더 좋은 성능을 기대할 수 있다.

(3) 퀵 정렬 (Quick Sort)

퀵 정렬 (quick sort)도 병합 정렬과 마찬가지로 '분할 정복'에 근거하여 만들어진 정렬 방법이다.
실제로 퀵 정렬 역시 정렬대상을 반씩 줄여가는 과정을 포함한다.
퀵 정렬은 이름이 의미하듯이 평균적으로 매우 빠른 정렬의 속도를 보이는 알고리즘이다.

1) 이해와 구현

퀵 정렬의 기본 원리를 오름차순 정렬을 기준으로 이해해보자.

No.	Pic.	Expl.
1. 초기화		퀵 정렬의 대상이 되는 배열. 퀵 정렬을 위해서는 총 5개의 변수 left, right, pivot, low, high를 선언해야 함. - left : 정렬대상의 가장 왼쪽 지점을 가리키는 이름 - right : 정렬대상의 가장 오른쪽 지점을 가리키는 이름 - pivot (피벗) : 중심점, 중심축 (기준) 현재는 가장 왼쪽에 위치한 데이터(5)를 피벗으로 결정 - low : 피벗을 제외한 가장 왼쪽에 위치한 지점을 가리키는 이름 - high : 피벗을 제외한 가장 오른쪽에 위치한 지점을 가리키는 이름
2. low와 high의 이동		(오름차순 기준) - low의 오른쪽 방향 이동 : 피벗보다 큰 값을 만날 때까지 - high의 왼쪽 방향 이동 : 피벗보다 작은 값을 만날 때까지 (일반화) - low의 오른쪽 방향 이동 : 피벗보다 정렬의 우선순위가 낮은 데이터를 만날 때까지 - high의 왼쪽 방향 이동 : 피벗보다 정렬의 우선수위가 높은 데이터를 만날 때까지 low와 high의 이동은 별개로 같이 한 칸씩 이동할 필요 없음.
3. low와 high의 교환		이전 단계에서 피벗을 기준으로 low는 피벗보다 큰 값을 만날 때까지, high는 피벗보다 작은 값을 만날 때까지 이동하면 low는 7에서 멈추게 되고, high는 4에서 멈추게 됨. low와 high의 데이터 교환. 교환이 된 이후 low와 high 이동 계속 진행. low와 high가 가리키는 위치가 교차될 때까지 진행.
4. 피벗의 이동		피벗과 high가 가리키는 데이터를 서로 교환. 여기까지가 1회전. 피벗이었던 5의 정렬 완료. 5를 기준으로 왼쪽 영역과 오른쪽 영역으로 나뉘게 됨. 왼쪽 영역은 피벗인 2를 기준으로 퀵 정렬 진행. 오른쪽 영역은 피벗인 9를 기준으로 퀵 정렬 진행. left와 right가 각각 정렬대상의 시작과 끝을 의미하기 때문에 이 과정은 left > right (left와 right가 교차되는 상황)이 될 때까지 진행.

위에서 설명한 과정을 함수로 구현해보자.
병합 정렬에서 두 배열을 합치는 MergeTwoArea 함수에 비하면 간단하다.

void Swap(int arr[], int idx1, int idx2)
{
    int 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++;          // low를 오른쪽으로 이동
        
        // 피벗보다 작은 값 찾기
        while(pivot < arr[high])
            high--;         // high를 왼쪽으로 이동
        
        // low와 high가 교차되지 않은 상태, Swap
        if(low <= high)
            Swap(arr, low, high);
    }

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

여기서 Partition이란 함수는 이 함수가 반환하는 값은 제 자리를 찾은 피벗의 인덱스 값이기 때문에 이 값을 기준으로 정렬의 대상은 왼쪽 영역과 오른쪽 영역으로 나뉘게 된다는 것을 알 수 있다.
다음은 퀵 정렬을 구현한 함수다.

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

반으로 나눈 각각의 영역에서 재귀적인 형태의 함수호출을 통해 각각 정렬하는 것을 알 수 있다.
여기서 if문의 조건은 left > right (left와 right가 교차되는 상황)이 되면 정렬을 종료한 다는 것을 의미하고 있다.

이제 구현한 함수들을 실행할 수 있는 실행파일 전체를 작성하면 다음과 같다.

#include <stdio.h>

void Swap(int arr[], int idx1, int idx2)
{
    int 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++;          // low를 오른쪽으로 이동
        
        // 피벗보다 작은 값 찾기
        while(pivot < arr[high])
            high--;         // high를 왼쪽으로 이동
        
        // low와 high가 교차되지 않은 상태, Swap
        if(low <= high)
            Swap(arr, 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()
{
    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

여기서 주석으로 해놓은 int arr[3] = {3, 3, 3}; 상황으로 변경해서 적용하면 코드의 버그로 인해서 Partition 함수를 빠져나오지 못해 무한루프가 생성된다.
왜냐하면 pivot == arr[low] == arr[high]상태가 디기 때문에 while 조건이 항상 거짓이 되고 low는 증가의 기회를, high는 감소의 기회를 얻지 못한다.
따라서 바깥족의 while문을 빠져나가지 못해 무한 루프에 갇힌 것이다.

이 부분은 아래와 같이 변경하게 되면 저장된 세 개의 데이터가 같은 상황에서도 진행이 될 수 있다.

int Partition(int arr[], int left, int right)
{
	....
    while(low <= high)
    {
    	while(pivot >= arr[low] && low <= right)
        	low++;
        
        while(pivot <= arr[high] && high >= (left+1))
        	high--;
        ....
    }
    ....
}

이렇게 바꾸게 되면 low와 high는 각각 증가와 감소의 기회를 얻고 각 방향으로 이동할 수 있게 된다.
그리고 추가된 조건이 하나 더 있는데 이는 경계검사를 위한 연산이고 left+1은 피벗을 제외하기 위함이다.

마지막으로 피벗의 선택에 대해서 더 생각해보자.
가장 왼쪽에 위치한 데이터를 피벗으로 결정하였지만 실은 전체 데이터를 기준으로 중간에 해당하는 값을 피벗으로 결정할 때 더 좋은 성능을 보인다.
왜냐면 피벗이 중간에 해당하는 값일 경우 정렬대상이 균등하게 나뉘기 때문이다.
정렬의 과정에서 선택되는 피벗의 수는 앞서 정의한 Partition 함수의 호출횟수를 의마한다.
그리고 Partition 함수의 호출횟수가 많다는 것은 그 만큼 데이터의 비교 및 횟수가 증가함을 의미한다.
즉, 좋은 성능을 보이려면 최대한 중간 값에 가까운 피벗이 지속적으로 선택되어야 한다.
이를 위해서 정렬대상에서 세 개의 데이터를 추출한 후 그 중에서 중간 값에 해당하는 것을 피벗으로 선택하는 방법을 사용한다.
이 방법을 사용하면 중간에 가까운 값을 선택할 확률이 높아지고 이에 따른 추가 연산이 필요하지만 특정 위치의 값을 무조건 피벗으로 결정하는 것보다 좋은 성능을 가질 수 있다.

2) 성능 평가

먼저 퀵 정렬의 비교연산 횟수를 알아보자.

피벗이 결정되면 low는 오른쪽으로, high는 왼쪽으로 이동하기 시작한다.
그리고 이동은 low와 high가 역전될 때까지 진행된다.
이동의 과정에서 피벗과의 비교를 매번 수반하므로 하나의 피벗이 제 자리를 찾아가는 과정에서 발생하는 비교연산의 횟수는 데이터의 수에 해당하는 $n$ 라고 할 수 있다.
물론 피벗보다 하나 적은 $n-1$ 라고 해도 되지만 1은 무시해도 되는 작은 수기 때문에 $n$ 라고 한다.
이러한 비교연산의 횟수는 다음과 같이 정렬의 범위가 분할된 상태에서도 마찬가지다.

반으로 나뉜 상태에서 각각의 low와 high가 각각의 방향으로 이동하는데 이때도 비교연산이 진행되니 비교연산의 횟수는 데이터의 수에 해당하는 $n$ 라고 할 수 있다.

이제 분할이 몇 단계에 걸쳐서 이뤄지는가를 생각해보자.
예시로 31개의 데이터를 대상으로 퀵 정렬을 진행한다고 생각해보자.
피벗이 항상 중간 값으로 결정되는 이상적인 경우라고 생각한다면 처음에 15개씩 두 개로 나뉠 것이고, 이어서 이들은 각각 다시 7개씩 두 개로 나뉠 것이다.

이 횟수는 $k = log_2n$ 이 될 것이고
따라서 비교연산의 빅-오는 $O(nlog_2n)$ 이 된다.

하지만 이 빅-오는 이상적인 상황에서의 빅-오기 때문에 최악의 상황에서의 빅-오를 알아봐야하지 않을까?
최악의 경우 비교 연산의 횟수는 데이터 수와 동일하게 $n$ 가 된다.
이는 단순한 정렬 알고리즘에서 많이 봐 온 빅-오 복잡도이다.
하지만 퀵 정렬은 실제로 $O(nlog_2n)$ 의 복잡도를 갖는 다른 정렬 알고리즘과 비교했을 때에도 평균적으로 가장 빠른 것으로 알려져 있다.
그리고 그 이유를 퀵 정렬의 데이터 이동횟수가 상대적으로 적고, 병합 정렬과 같이 별도의 메모리 공간을 요구하지 않는다는 사실에서 알 수 있다.
따라서 다른 정렬 알고리즘 중에서 평균적으로 가장 빠른 정렬속도를 보이는 알고리즘이다.

(4) 기수 정렬(Radix Sort)

기수 정렬 (radix sort)에서 기수(radix)란 주어진 데이터를 구성하는 기본 요소를 의미한다.
예를 들어서 2진수는 0과 1의 조합으로 데이터를 표현하니 2진수의 기수는 0과 1이다.
유사하게 10진수는 0과 9까지의 숫자가 10진수의 기수가 된다.
따라서, 기수 정렬은 데이터를 구성하는 기본 요소, 즉 기수를 이용해서 정렬을 진행하는 방식이다.
그리고 기수 정렬은 정렬순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않는다.

이게 어떤 의미일까?
비교연산은 정렬 알고리즘의 핵심이라 할 수 있다.
두 데이터 간의 정렬순서상 우선순위를 판단하기 위한 비교연산은 핵심중의 핵심이다.
따라서 앞에 배운 모든 정렬 알고리즘들은 이 연산을 포함하고 있고 알고리즘의 복잡도도 이 연산을 근거로 판단해왔다.

그리고 기수 정렬은 정렬 알고리즘의 이론상 성능의 한계인 $O(nlog_2n)$ 라는 빅-오 복잡도를 넘어설 수 있는 유일한 알고리즘이다.

단, 적용할 수 있는 범위가 제한적이란 단점이 있다.
예를 들어 배열에 저장된 1, 7, 9, 5, 2, 6을 오름차순으로 정렬하는 경우, 영단어 red, whe, zoo, box를 사전편찬 순서대로 정렬하는 경우 기수 정렬로 해결할 수 있다.

반면 배열에 저장된 21, -9, 125, 8, -136, 45를 오름차순으로 정렬하는 경우, 영단어 professionalism, few, hydroxproline, simple을 사전편찬 순서대로 정렬하는 경우 기수 정렬로 해결할 수 없다.

데이터의 길이가 같은 대상으로는 정렬이 가능하지만, 길이가 같지 않은 데이터들을 대상으로 기수 정렬의 적용이 어렵다.

물론 방법은 있겠지만 그렇게 하기 위해서는 데이터 가공을 위한 별도의 알고리즘이 필요하고 이 알고리즘의 적용으로 인한 효율 문제도 고려해야한다.
이렇게 될 경우 기수 정렬대신 다른 정렬을 적용하는 것이 훨씬 더 효율 적일 수도 있다.

1) 이해

기수 정렬 과정에 대해 이해해보자.

위 그림은 한자리 정수(10진수)에 대해 기수 정렬을 바탕으로 정렬되는 과정을 보여준다.
10진수 정수의 정렬을 위해서는 총 10개의 버킷(양동이)가 필요하고 버킷은 0부터 9까지 순서대로 이름이 매겨져 있다.
정렬대상은 값에 해당하는 버킷으로 이동한다.
버킷으로의 이동이 끝났다면 버킷 0에 저장된 것부터 시작해서 버킷 9에 저장된 것까지 순서대로 꺼내서 차례로 나열만 하면 된다.
이것이 기수 정렬의 기본 원리다.

기수 정렬로 세 자릿수 10진수 정수들을 정렬할 때에도, 다섯 자리 정수들이라고 해도 버킷은 기수의 개수인 10개가 필요하다.
영단어를 정렬하려면 아스키 코드에서 영단어에 해당하는 만큼 버킷이 필요하다.
따라서 이 부분도 기수 정렬의 단점이 될 수 있다.

2) LSD vs. MSD

기수 정렬의 구현을 목적으로 다음 세 자리수 정수들을 대상으로 기수 정렬을 진행해보자.
오름차순으로 정렬하며 이 세자리 정수들은 10진수가 아닌 5진수로 표현되어 있다.
따라서 5개의 버킷만을 가지고 기수 정렬을 진행한다.

134, 224, 232, 122

지금부터 사용하는 방법을 가리켜 'LSD 기수 정렬'이라 한다.
'LSD'란 Least Significant Digit의 약자로 덜 중요한 자리수에서부터 정렬을 진행해 나간다는 의미다.
쉽게 말해 첫 번째 자리수부터 시작해서 정렬을 진행해 나간다.

No.	Pic.	Expl.
1		첫 번째 자리수를 기준으로 하여 134와 224를 순서대로 버킷 4에 넣고 이어서 232와 122를 버킷 2에 넣기. 버킷 0에서부터 시작해 데이터를 꺼낸다. 하나의 버킷에 둘 이상의 데이터가 존재하는 경우 들어간 순서대로 꺼내기. 232, 122, 134, 224순으로 데이터 정렬.
2		두 번째 자리수를 기준으로 하여 정렬 진행. 122, 224, 232, 134순으로 데이터 정렬.
3		마지막으로 세 번째 자리수를 기준으로 하여 정렬 진행. 122, 134, 224, 232로 정렬 완료.

이 방법의 단점은 작은 자릿수에서 시작해서 가장 큰 자릿수까지 모두 비교를 해야 값의 대소를 판단할 수 있다.
비교 중간에 대소를 판단하는 것은 불가능하다.
가장 영향력이 큰 자릿수를 마지막에 비교하니 마지막까지 결과를 알 수 없는 것이 이 방법의 단점이다.

이번에는 LSD와 반대 방향으로 정렬을 진행하는 MSD 기수 정렬에 대해 알아보자.
'MSD'란 Most Significant Digit의 약자로써 가장 중요한 자릿수, 즉 가장 큰 자릿수에서부터 정렬을 진행하는 것이다.
그렇다면 LSD와 방향만 다르고 정렬의 과정이 같을까?
아니다.

LSD와 같은 방식으로 정렬을 진행하면 위와 같이 정렬이 완료되지 않는다는 것을 알 수 있다.
MSD방식은 LSD 방식과 달리 첫 번째 과정만 거쳐도 대략적인 정렬의 결과가 눈에 보인다.
즉, LSD는 마지막에 가서 정렬순서를 판단하는 방식이고, MSD는 점진적으로 정렬을 완성해가는 방식이다.
MSD 방식의 가장 큰 장점은 반드시 끝까지 가지 않아도 되고 중간에 정렬이 완료될 수도 있다는 것이다.
하지만, 모든 데이터에 일괄적인 과정을 거치게 (재귀적 호출) 할 수 없다는 단점이 있다.
따라서 구현의 난이도가 LSD에 비해 상대적으로 높고 중간에 데이터가 잘 정렬되고 있는지 점검해야 하므로 성능의 이점도 반감될 수 있다.

3) LSD 기준 구현

일반적으로 기수 정렬이라 하면 LSD 방식을 기준으로 얘기한다.
구현의 편의성이 가장 큰 이유이기도 하면서 MSD의 경우 정렬의 과정에서 모든 데이터에 일괄적인 과정을 거치게 할 수 없기 때문에 추가적인 연산과 별도의 메모리가 요구된다는 점이 있기 때문에 LSD방식으로 기수 정렬을 구현한다.
(참고로 LSD와 MSD의 빅-오는 같다.)

양의 정수라면 그 길이에 상관없이 정렬의 대상에 포함시킬 수 있는 기수 정렬을 구현해보자.
예를 들어 42, 715와 같은 두 정수를 정렬한다고 가정한다면
처음에는 2와 5를 가지고, 두번째에는 4와 1을 가지고 정렬을 진행한다.
그리고 마지막으로 0과 7을 추출해서 정렬을 진행한다.
각 수의 각 자리수를 추출하는 것이 포인트다. 따라서 각 자리수의 추출방법은 다음과 같다.

∙ NUM으로부터 첫 번째 자리 숫자 추출 NUM / 1 % 10
∙ NUM으로부터 두 번째 자리 숫자 추출 NUM / 10 % 10
∙ NUM으로부터 세 번째 자리 숫자 추출 NUM / 100 % 10

위 수식을 바탕으로 한 기수 정렬 구현은 다음과 같다.
참고로 버킷은 그 구조가 큐에 해당하기 때문에 앞에서 배운 '연결 리스트 기반의 큐'를 활용했다.
(ListBaseQueue.h, ListBaseQueue.c)

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

#define BUCKET_NUM 10

void RadixSort(int arr[], int num, int maxLen)
{
    // 매개변수 maxLen에는 정렬대상 중 가장 긴 데이터의 길이 정보가 전달
    Queue buckets[BUCKET_NUM];
    int bi;
    int pos;
    int di;
    int divfac = 1;
    int radix;

    // 총 10개의 버킷 초기화
    for(bi=0; bi<BUCKET_NUM; bi++)
        QueueInit(&buckets[bi]);

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

            // 추출한 숫자를 근거로 버킷에 데이터 저장
            Enqueue(&buckets[radix], arr[di]);
        }

        // 버킷수만큼 반복
        for(bi=0, di=0; bi<BUCKET_NUM; bi++)
        {
            // 버킷에 저장된 것 순서대로 다 꺼내서 다시 arr에 저장
            while(!QIsEmpty(&buckets[bi]))
                arr[di++] = Dequeue(&buckets[bi]);
        }

        // N번째 자리의 숫자 추출을 위한 피제수의 증가
        divfac *= 10;
    }
}

int main()
{
    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;
}

> gcc .\ListBaseQueue.c .\RadixSort.c    
> .\a.exe
> 출력
6 13 14 15 212 7141 10987

위 함수 RadixSort는 길이가 가장 긴 데이터의 길이 정보를 전달받도록 정의했다.
함수 내에서 길이 정보를 직접 계산해서 구현할 수도 있지만 불필요한 연산을 수반할 수 있기 때문에 직접 입력으로 진행했다.

4) 성능 평가

기수 정렬은 비교연산이 핵심이 아니다.
오히려 버킷으로의 데이터 삽입과 추출이 핵심이다.
따라서 이 정렬의 시간 복잡도는 삽입과 추출의 빈도수를 대상으로 결정해야 한다.
버킷을 대상으로 하는 데이터의 삽입과 추출을 한 쌍의 연산으로 묶으면 이 한 쌍의 연산이 수행되는 횟수는 $maxLen × num$ 이 된다.
정렬대상의 수가 $n$ 이고, 모든 정렬대상의 길이가 $l$ 이라 할 때, 시간 복답도에 대한 기수 정렬의 빅-오는 $O(nl)$ 이 된다.
이는 상수 $l$ 을 무시하고 $O(n)$ 로 봐도 되고 퀵 정렬의 복잡도인 $O(nlog_2n)$ 보다 뛰어난 성능임을 알 수 있다. (물론 적용 가능한 대상이 제한적이라는 단점이 있지만!)

`<Reveiw>`

이렇게 다양한 정렬 알고리즘에 대해서도 알아봤다.
더 다양한 정렬 방법이 있지만 내가 아는 c언어 수준에서는 이정도까지 적당한 것 같다 ㅎㅎ
파이썬으로 구현한 다양한 정렬도 궁금하다면 이 글📚을 읽어보는 것도 추천한다.

이제 본격적으로 탐색(Search)를 시작해보자!

김민정

백엔드 코린이😁

이전 포스트

Chapter 09. 우선순위 큐(Priority Queue)와 힙(Heap)

다음 포스트

Chapter 10. 정렬(Sorting)

윤성우 열혈 자료구조

10-1. 단순한 정렬 알고리즘

(1) 버블 정렬 (Bubble Sort)

1) 이해와 구현

2) 성능 평가

(2) 선택 정렬 (Selection Sort)

1) 이해와 구현

2) 성능 평가

(3) 삽입 정렬 (Insertion Sort)

1) 이해와 구현

2) 성능 평가

10-2. 복잡하지만 효율적인 정렬 알고리즘

(1) 힙 정렬 (Heap Sort)

1) 이해와 구현

2) 성능 평가

(2) 병합 정렬 (Merge Sort)

1) 이해와 구현

2) 성능 평가

(3) 퀵 정렬 (Quick Sort)

1) 이해와 구현

2) 성능 평가

(4) 기수 정렬(Radix Sort)

1) 이해

2) LSD vs. MSD

3) LSD 기준 구현

4) 성능 평가

`<Reveiw>`

Chapter 09. 우선순위 큐(Priority Queue)와 힙(Heap)

Chapter 11. 탐색(Search) 1

0개의 댓글