10. Sort #2 Complex Sort Algorithm1

1. Heap Sort

1) Heap

Heap은 우선순위 큐를 구현할 때 사용했던 자료구조이다. (앞의 CH9)

부모노드의 우선순위가 자식노드 각각의 우선순위보다 높도록 구성되어 있다. 이런 Heap정렬에서 데이터를 삭제는 상황에서는 루트노드(= 노드 중 가장 우선순위가 높은 노드)를 부터 진행한다.

2) Heap Sort

따라서 Heap을 이용한 정렬은 가지고 있는 데이터를 모두 힙에 넣은 후, 하나씩 삭제하며 빼는 과정을 거치면 된다. 단순히 데이터를 넣었다가 꺼내기만 했는데도 정렬이 되는 이유는, 힙에 저장하는 과정 자체가 ‘우선순위를 고려’ 했기 때문이다. 책의 앞부분에서 정렬, 탐색과 같은 알고리즘을 구현할 때 중요한 것은 ‘어떻게 꺼낼까’ 보다, ‘어떻게 저장할까?’라고 했다.

잘 저장하면, 단순히 꺼내기만 하는 과정을 통해서도 정렬이 가능함을 알 수 있었다.

void HeapSort(int arr[], int n, PriorityComp pc){
    ....
    for(i=0;i<n;i++)
        HInsert(&heap, arr[i]);

    for(i=0;i<n;i++)
        arr[i]=HDelete(&heap);
}

3) Quality Evaluation

성능평가를 하기 위해 핵심적인 계산들에 대해 알아보자.

1. Heap자료구조의 성능

힙자료구조에서 핵심 계산은 ‘저장’과, ‘삭제’(=꺼내기)다.

우린 앞서 힙의 데이터 저장, 삭제의 시간복잡도를 O( log 2 n)으로 계산한 적이 있었다.

1. Heap 정렬의 성능

그렇다면 Heap정렬의 성능에 대해 알아보자. heap정렬에서 n개의 데이터를 사용한다면, n번 삽입, 삭제를 진행해야 한다. 따라서 시간복잡도는 O(nlog2n)이라고 할 수 있다.

근데 엄밀히 따지자면, n을 냅다 곱해버리는 것은 무책임하다.

n개의 데이터를 삽입한다 했을 때

1개째 → 시간복잡도 log1

2개째→ 시간복잡도 log2

3개째 → 시간복잡도 log3

이렇게 된다면 우린 시간 복잡도를

이처럼 sigma를 씌운 값으로 계산해야 한다. (시간복잡도는 매 순간 일정하지 않기 때문에. 점진적으로 커지는 것이기 때문에)

sigma를 적분으로 근사시켜 계산하면

이런 결과로, 결국 O(nlogn)이라고 할 수 있다.

암튼,, 결론은 n을 곱한게 맞지만, 과정은 단순히 ‘n번 삭제삽입 하니까 곱해주자’로 접근하면 안된다는 것이다.

2. Merge Sort

1) Definition && Flow

처음에 병합정렬 배울 때 굉장히 헷갈렸던 거 같다.

이 그림을 보고 혼란스러워 했던 기억이 있는데, 돌이켜 보면, 병합정렬을 ‘반복’해서 정렬을 완성하는 것이 아니라, 저 그림의 과정을 마지막 한 번만 사용한다 생각하여 헷갈렸던 것 같다.

그림에서 보이는 4개로 구성된 배열 두 개를 병합하는 과정을 보면, 병합이 어떤식으로 진행되는지 확인할 수 있다. 이 원리를 바탕으로 앞서 1+1→2개로 병합할 때도, 2+2→ 4개로 병합할 때도 동일한 방식을 취해주면 되는 것이다

차라리 2단계 정렬 → 3단계 결합 두 단계만 보여줬으면 덜 헷갈렸을 것 같다. 2단계 정렬은 분할 + 정렬 과정을 안보여주고 바로 정렬된 결과가 나와버려 헷갈렸다.

병합정렬은 크게 보면 분할하는 과정과, 병합하는 과정으로 나누어볼 수 있다.

초반에는 최소단위(=1개)까지 쪼개질 수 있도록 분할을 하고, 중간부터는 병합만 한다.

병합하는 과정은 대상의 이가 어떠하던 동일하게 진행된다. 병합의 원리를 알아보자.

2) MergeSort

(1) Function

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

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

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

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

이 MergeSort부분도 초반에 공부할 때 많이 헷갈렸었다. 특히나 재귀로 작성되어 있는 코드를 보고 혼란스러워했던 기억이 있다.

이걸 보니까 갑자기 어제 복습했던 재귀함수 부분이 기억났다

(2) Review..(Recursive func)

어제 복습겸 던 2진수 만들기 함수였다.

int binPrint(int n) {
    printf("0b");

    if (n == 1)
        printf("1");
    else if (n == 0)
        printf("0");
    else {
        int left = n % 2;
        printf("%d",left);
        binPrint(n / 2);
    }
}

처음에는 함수를 이렇게 만들었다. 출력을 하고 재귀함수를 호출하는 식으로 코드를 구성했더니, 원하는 결과가 ‘거꾸로’ 출력되었다. 난 순서상 먼저 계산이 이뤄지더라도, 나중에 출력되었으면 좋겠다.

숫자 출력 → 재귀 호출의 순서로 코드를 작성해서 문제가 생긴 것이기 때문에

재귀 호출 → 숫자 출력 의 순서로 코드를 수정하였다.

void print_binary(int n) {
    if (n == 0) {
        return; 
    }
    print_binary(n / 2); //recursive

    printf("%d", n % 2); //print
}

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

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

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

이것도 마찬가지다. 난 MergeSort함수 안에 MergeSort가 또 있어서 헷갈렸지만, 결국 마지막에 MergeTwoArea가 있다.

그렇다면 우선 계속해서 MergeSort를 하고, 가장 안쪽에서부터 MergeTwoArea가 진행된다고 보아도 괜찮을 것이다.

가장 안쪽 즉, if문의 조건을 만족하지 않는 상태는 언제일까?

 

 

MergeSort(arr,0,1) 처럼한 칸 차이가 나는 경우까지 가능하다. MergeSort(arr, n, n)부터는 자동으로 사라진다.

그렇다면 실행되는 순서는

MergeSort(arr,0,1)
MergeSort(arr,2,3)

MergeTwoArea(arr, 0, 1, 3)

MergeSort(arr,0,1)→MergeSort(arr,0,0) MergeSort(arr,1,1)

MergeTwoArea(arr, 0, 0, 1)

MergeSort(arr,2,3)→MergeSort(arr,2,2) MergeSort(arr,3,3)

MergeTwoArea(arr, 2, 2, 3)

 

MergeTwoArea(arr, 0, 0, 1)

MergeTwoArea(arr, 2, 2, 3)
MergeTwoArea(arr, 0, 1, 3)

 

마지막엔 결국 이런 MergeTwoArea들만 남는다.

MergeSort는 사실상 MergeTwoArea를 발생시키 위한 단계인 것이다.

 

(3) MergeTwoArea

지금부터 MergeTwoArea의 역할에 대해 확인해보자.

MergeTwoArea(arr[], right, mid, left)는 arr에서 정렬되어 있는 부분(right,

mid, mid+1,

left) 두 배열을 병합하는 함수다.

int fIdx = left;
int rIdx = mid + 1;

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

1. fIdx, RIdx에 각 배열의 맨 앞머리 index값을 할당한다.
2. sortArr : 결과 할당

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

1. while() : 첫 번째 배열이나, 두 번째 배열이 끝나기 전 까지sIdx++ : sIdx즉, 결과값을 넣을 index를 한 칸 늘린다.
2. if : fIdx값이 적다 = fIdx가 가리키는 element의 우선순위가 높은 경우 → sortArr 즉, 결과값에 fIdx의 요소를 할당한다.

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

if (fIdx > mid) : 앞의 배열이 끝난 경우

for.. : rIdx(=뒷배열의 시작점) 부터 ~ right(=뒤 끝까지) 즉, 뒷배열의 남은 부분 모두 결과값에 넣기

이미 정렬이 되어 있는 상태일 것이므로 상관없음

<사진>

MergeTwoArea(arr[], right, mid, left)

즉, 이미 정렬되어 있는 배열 두 개를 병합하되, 두 배열의 요소를 하나씩 비교하여 우선순위를 비교한 후 결과 값에 할당하는 것이다. 이 결과 arr배열의 right부터 left까지 정렬되어 있을 것이다.

(4) Implementing

MergeTwoArea(arr, 0, 0, 1)//0~1 정렬 1+1

MergeTwoArea(arr, 2, 2, 3)//2~3정렬 1+1

MergeTwoArea(arr, 0, 1, 3)//이미 정렬된 0

1, 2

3을 모아서 다시 정렬 2+2

 

 

 

Merge Sort에서 헷갈렸던 부분 중심으로 정리하면

MergeTwoArea는, 세 개의 index를 중심으로 생성된 두 개의 정렬된 배열을 다시 병합하는 함수다
MergeSort는, MergeTwoArea함수가 적절한 상황에, 적절한 횟수만큼 실행될 수 있도록 하는 재귀함수임
MergeSort의 방식

 

3) Quality Evaluation

성능평가를 위해 핵심 계산인 비교연산의 횟수와, 이동연산의 횟수를 계산해보자.

그런데, 아까 작성했던 것 처럼 병합정렬의 핵심은 ‘MergeTwoArea’에 있다.

1+1=2가 되는 병합연산에선 비교과정이 두 번 진행된다 (if && else)

→ 이걸 두 번이라고 보는 것은 아까와 다르다고 생각할 수 있는데, 사실 n배 하는 것은 bigO를 구하는 데 큰 의미가 없다.

8개의 Element가 있다 가정했을 때

 

1+1=2로 4개의 묶음을 만드는 데 사용된 비교 횟수는 8번이다.

 

2개씩 4묶음이 있을 때

2+2=4로 2개의 묶음을 만드는 데 사용된 비교 횟수는 4번이다.

 

즉 병합해야 하는 대상의 개수만큼 최대 비교 횟수가 발생한다.따라서 빅오는

O(nlog2n)이다.