211213, 자료구조 Ch.10-1

주말 잘 쉬고 왔다. 공부 시작.

Ch.10 정렬 (Sorting)

정렬. 이름 그대로 정렬한다.

그 정렬과 관련된 알고리즘들을 알아보자.

10-1

우선, "단순한" 정렬 알고리즘들 부터.

Bubble Sort

버블 정렬이라고 한다. 배열에서 인접한 두개의 데이터를 "일일히" 비교해가며 정렬을 진행한다.

출처

#include <stdio.h>

void Bubble(int arr[], int n) { // n은 배열의 요소 갯수.

    int i, j;
    int temp;
    // 오름차순이라 가정함.
    for (i=0 ; i<(n-1) ; i++) {
        for (j=i+1 ; j<(n-i)-1 ; j++) {
            if (arr[i] > arr[j]) {
            // 만약 앞의 요소가 뒤의 요소보다 값이 크면 서로 교체
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }

}

int main() {

    int arr[4] = {7, 6, 4, 3};
    int i;
    
    Bubble(arr,sizeof(arr)/sizeof(int));
    
    for (i=0 ; i<4 ; i++) {
        printf("%d ", arr[i]);
    }
    
    printf("\n");
    return 0;

}

위의 그림은 7, 6, 4, 3이라는 배열을 예시로 들며 정렬하는 과정을 나타낸 그림과 이 과정을 구현한 코드다.

물론, 이 코드 자체는 구현하는데 그렇게 어려움이 없다. 하지만, 프로그래밍에서의 국룰. "사용하기 쉬우면 그만한 단점이 있다."

성능

자료구조 공부 초반에 성능 평가의 요소중 Key Point 가 시간 복잡도 (빅-오) 를 통해 평가하는 곳이라고 말 한 적이 있다.

이런 정렬 알고리즘의 성능은 두가지 평가요소가 있다.

1. 비교의 횟수 : 비교를 몇번이나 했냐
2. 정렬의 횟수 : 위치 변경을 몇번이나 했냐

1번 비교의 횟수는 위 코드에서 어디에서 평가할 수 있을까?

if (arr[i] > arr[j])

여기다. 두 수의 크기를 비교하는 연산은 여기밖에 없으니까!

만약 위처럼 데이터가 네개가 있다고 할 때, 최악의 상황. 즉 비교 연산을 최대한 많이하는 경우를 보자.

그러면 처음엔 세번, 두번째턴은 두번, 세번째턴은 한번일 것이다. (위의 버블 정렬 그림 예시를 보도록 하자)

그러면, 데이터 갯수 4를 기준으로 3, 2, 1번..

데이터 갯수 n을 기준으로 (n-1), (n-2), (n-3)번.. ㅇ?

어디서 많이 봤지 않나?

등차수열의 합과 같다!

그래서 이 식을 Big-Oh 표기법으로 나타내면, 최고차항의 계수를 날리고, 그 최고차항만 써먹으면

비교 연산 횟수에 대한 시간 복잡도는 이렇게 된다. 썩 좋지는 않다.

그리고, 이동 연산에 대한 빅-오는?

비교 연산 횟수와 같다. 최악의 상황에는 비교 연산을 1번 진행해서 바꿔야 한다고 인식할 때 마다 이동도 1번 진행하니까.

그래서 이동 연산에 대한 빅-오도

로 같다.

실제로는 최악의 경우를 따지면 데이터 이동 = 비교 횟수 x 3 이라지만, 계수는 어짜피 날려버리니 무시한다.

Selection Sort

선택 정렬. "정렬 순서에 맞게 하나씩 선택해서 옮기고, 옮기며 정렬이 되게한다".

그림을 보면 이해하기 쉬울거다.

화살쵸 우측에서 좌측의 배열이 SortedArray, 우측이 UnsortedArray로 나뉜다. 이 말인 즉슨, 정렬의 결과인 SortedArray를 담을 별도의 메모리 공간이 필요해진다.

그러면, 구현된 코드도 보도록 하자.

#include <stdio.h>

void Selection(int arr[], int n) {

    int i, j;
    int maxIdx; // SortedArr을 만들기 위해 필요한 인덱스값
    int temp;
    
    for (i=0 ; i<n-1 ; i++) {
        maxIdx = i;
        
        for ( j=i+1 ; j<n ; j++) {
            if (arr[i] > arr[j]) { 
            // 만약 앞의 요소가 뒤의 요소보다 크다면
                maxIdx = j; // 뒤의 요소의 인덱스 값을 maxIdx에 저장
            }
        }
        // j for문이 끝나면
        // UnsortedArr의 가장 작은 값의 인덱스 값이 maxIdx에 남는다
        
        temp = arr[i];
        arr[i] = arr[maxIdx];
        arr[maxIdx] = temp; // i for문이 진행되며 SortedArr에 값을 쌓아나감  
    }
}

int main() {
    int arr[4] = {7, 5, 4, 2};
    
    Selection(arr, sizeof(arr)/sizeof(int));
    
    for (int i=0 ; i<4 ; i++) {
        printf("%d ", arr[i]);
    }
    
    printf("\n");
    return 0;
}

성능

앞의 버블 정렬처럼, 비교 / 이동 연산 기준으로 시간복잡도를 알아보자.

우선, 비교 연산.

if (arr[i] > arr[j])

이건 앞의 버블 정렬과 같다.

만약 데이터가 4개라면, 최악의 경우엔 비교 연산이 3번, 2번, 1번이다.

앞과 마찬가지. 비교에 따른 Big-Oh는

얘다.

그리고, 이동 연산.

temp = arr[i];
arr[i] = arr[maxIdx];
arr[maxIdx] = temp;

얘는 안쪽 for문인 j가 아닌 바깥쪽 for문인 i에 있다.

데이터가 n개라면, 총 n-1 번의 교환으로 끝이 난다. 이동 횟수는 명령문이 총 세줄이니, (n-1) * 3. 즉 3(n-1)이 된다.

근데 계수 다 날리가 최고차항의 차수가 Big-Oh니깐, 결과는

이 된다.

버블 정렬 "보단" 좋지만, 아직 비교연산이 n의 2승이라는 쉽지 않은 성능을 가지고 있어서, 패스하도록 하자.

Insertion Sort

삽입 정렬. 선택 정렬과 유사한데 다르다. 한번 보도록 하자.

각 각 데이터를 비교하며 정렬된 상태가 되도록,데이터를 옮겨주며 정렬하는 방식이다.

아마 얘는 앞의 정렬들보다 조금 직관적이지 않아서, 추가 설명을 그림으로 더 자세히 보여주겠다.

이 정렬의 핵심은 다음과 같다.

"정렬이 완료된 영역의 다음 데이터가 그 다음 정렬 대상"

"삽입할 위치를 발견하고, 데이터를 한 칸씩 뒤로 밀 수도 있지만, 데이터를 한 칸씩 뒤로 밀며 삽입할 위치를 찾을 수도 있다."

#include <stdio.h>

void Insert(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;
        }

}

.. main은 위의 예제들과 거의 동일하여 생략하겠음

위의 코드와 그림이 조금 설명하는데 있어서 다를 수 있지만, 일일히 그려나가며 과정을 나열해보면 아마 의미상 비슷할거다.

insData 에 비교할 메인 대상을 저장해 놓고, arr[j]를 통해 앞에 있는 친구들과 하나씩 비교한다는 얘기니까.

성능

비교연산은

if (arr[j] > insData)

이다. 그리고

이동연산도 위의 비교연산 if문 안에서

arr[j+1] = arr[j];

로 똑같은 횟수로 진행된다는 것을 알 수도 있다.

그러면 데이터 수가 n개라면 1번, 2번, 3번 ..., n-1번, n번으로 진행될 것이고, 등차수열의 합과 같으니 이 정렬의 비교 / 이동 연산 Big-Oh는

가 된다. 역시나, 그렇게 효율적이진 않다.

10-2

이번엔, 앞선 친구들보단 조금 복잡한 코드지만, 효율적인 알고리즘들을 살펴보겠다.

Heap Sort

힙 정렬. 얼레? 힙이 또 나왔네.

생각해보면, 이 힙 정렬도 위에서 말한 알고리즘들의 정렬 방법과 유사한 특징을 가지고 있다.

"루트 노드에 저장된 값 (진짜 순수 값이든, 우선순위든)이 가장 커야한다"

그러면 루트노드의 자식들을 차례대로 내려가면서 차곡차곡 정렬해주면 오름차순이든 내림차순으로 정렬할 수 있다는 것이다.

그러면 이 루트노드에 저장된 값을 "우선순위"라 생각하고, 이 코드를 한번 보자.

#include <stdio.h>
#include "RealHeap.h"
// 09-2에서 복습했던 우선순위를 알아서 매겨주는 heap의 헤더 파일을 포함한다
// 그리고 ReapHeap.c의 typedef char HData를 typedef int HData로 바꿔준다.

int Comp(int d1, int d2) {
    return d2 - d1;
} // d1이 더 크면(우선순위가 낮으면) 음수, d2가 더 크면(우선순위가 낮으면) 양수 반환

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() {
    arr[6] = {3, 8, 2, 4, 9, 7};
    int i;
    
    HeapSort(arr, sizeof(arr)/sizeof(int), Comp);
    
    for (i=0 ; i<4 ; i++) {
        printf("%d ", arr[i]);
    }
    
    printf("\n");
    return 0;
}

Heap에 대해 어느정도의 확실한 이해도가 있다면, 이 코드는 쉽게 이해할 수 있을 것이다.

성능

이 힙의 시간 복잡도는 위처럼 "비교", "이동"처럼 단순하게 얘기를 하기보단,

"데이터 삽입과 삭제를 통한 비교 연산", "데이터 정렬 과정을 통한 이동 연산" 이라고 보자.

우선, 첫번째.

우린 Heap에서 시간 복잡도에 대해 따졌던걸 기억하는가?

트리 높이가 하나 늘어날 때마다 비교 연산 횟수 1회 증가 = 데이터가 2배 늘어날 때마다 비교 연산 횟수 1회 증가. .. Ch.09-1 복습에서

이렇게 생각하면 데이터 삽입(저장)의 시간 복잡도는

데이터 삭제 시간 복잡도도 마찬가지로

이다.

그러면, 데이터 삽입 + 삭제를 묶어서 하나의 "비교 연산" 과정으로 보니까,

최종 시간복잡도는 O(log2n) x 2인데, 계속 말했다시피 계수는 무시하므로 최종적으로 비교 연산에 대한 시간 복잡도는

이다.

그러면, 정렬 과정을 통한 시간 복잡도는?

만약 정렬할 데이터 개수가 n개라 가정했을 때, 이 n개의 데이터에 대하여 데이터를 삽입/삭제 하므로 비교 연산에 대한 시간 복잡도에 n을 곱해주기만 하면 된다.

그러면 최종적으로

라는 결과가 나온다. 앞서 10-1에서 설명한 세개의 정렬보다 꽤 효율적이라는 것을 알 수 있다!

Merge Sort

이번엔 병합 정렬이다.

아마 앞선 친구들 + 힙 정렬에 비해서도 꽤 복잡할 수도 있다. 한번 익혀보자.

우선, 이 병합 정렬이라는 것을 이해하기 전에 "분할 정복"이라는 걸 먼저 알아야 한다. 이 분할 정복에 기반하여 병합 정렬이란 정렬방법이 만들어졌기 때문이다.

"분할 정복". "분할"하여 "정복" 한다고 생각하자.

1. 분할 (문제를 풀기 쉽게 분할해나감)
   -> 2. 정복 (최종적으로 분할된 문제를 해결한다)
   -> 3. 결합 (분할해서 해결한 결과물을 결합하여 최종 마무리)

이 순서대로.

이걸 정렬 방법에 빗대어보면

"8개"의 데이터를 한번에 정렬하기 보단, 둘로 나눠 "4개"의 데이터 정렬이 더 쉽고, 다시 둘로 나눠 "2개"의 데이터를 정렬하는 것이 더 쉽다.

아마 직관적으로 이해를 하긴 힘들거다. 이를 그림으로 나타내면 이렇다.

출처

어우.. 보기만 해도 조금 머리가 아프다. 뭘 이렇게 세세하게 분활을 한다냐.

이렇게 세세~하게 하나 하나가 남을 때 까지 분할을 해주는 이유는
★★★재귀적 구현을 위해서★★★이다.

솔직히 처음 봤을 떄 무슨 말인가 싶어서 엄청 고민고민했다.

자세한 내용은, 코드를 보자.

설명은 주석에 달겠다.

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

void MergeTwoArea (int arr[], int left, int mid, int right) {
    int fIdx = left; // 왼쪽 영역 (left~mid) 의 첫 번째 위치 정보.
    int rIdx = mid+1 // 오른쪽 영역 (mid+1~right) 의 첫 번째 위치 정보.
    int i;

    int *sortArr = (int *)malloc(sizeof(int)*(right+1));
    // 최종 결과가 저장될 배열 (정렬된 배열)을 동적할당 해준다.
    int sIdx = left;
    // sortArr 배열에 첫번째 요소부터 결과를 차곡차곡 정렬해야한다.

    while (fIdx <= mid && rIdx <= right) {
    // 좌 / 우측 영역의 데이터들을 비교한다.
    // 만약 좌측 영역의 데이터들을 전부 넣었으면 fIdx가 mid값을 넘어버려서 반복문 중지
    // 만약 우측 영역의 데이터들을 전부 넣었으면 ridx가 right값을 넘어버려서 반복문 중지
        if (arr[fIdx] <= arr[rIdx]) {
            sortArr[sIdx] = arr[fIdx++];
        } else {
            sortArr[sIdx] = arr[rIdx++];
        }

        sIdx++;
    }

    // 여기부터 사용하는 "남은 데이터"는 무조건 우선순위가 낮은 데이터들이 남게 된다.
    //그래서 크게 신경쓰지 말고 그냥 뒤에 넣자.

    if (fIdx > mid) {
    // If 좌측영역의 데이터들을 전부 넣었을 때, 남은 우측 데이터 넣기
        for (i=rIdx ; i<=right ; i++, sIdx++) {
            sortArr[sIdx] = arr[i];
        }
    } else {
    // If 우측영역의 데이터들을 전부 넣었을 때, 남은 좌측 데이터 넣기
        for (i=fIdx ; i<=mid ; i++, sIdx++) {
            sortArr[sIdx] = arr[i];
        }
    }

    for (i=left ; i <= tight ; i++) {
        arr[i] = sortArr[i];
    }

    free(sortArr);

}

void MergeSort (int arr[], int left, int right) {
// left, right로 정렬의 "범위"를 지정해준다.

    int mid; // 배열의 중간의 index값.

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

        MergeSort(arr, left, mid); // left ~ mid 까지를 다시 분할해준다.
        MergeSort(arr, mid+1, right);
        // mid 다음 위치인 mid+1 ~ right 까지를 다시 분할해준다.
        // 쭉-쭉 재귀적으로 나뉘어진다.
        //결과론적으론 모든 배열의 요소들이 하나씩 하나씩 다 분할될 것이다.

        MergeTwoArea(arr, left, mid, right);
        // 분할된 데이터들이 left~mid / mid+1~right 으로 나뉘어져 있으므로, 이를 결합해준다.
    }
}

int main() {

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

위의 MergeTwoArea에서 fIdx, rIdx에 대해 의아해 할 수 있으니 그림 설명을 추가하겠다.

위의 그림처럼, 쭉 쭉 비교가 진행되다가 rIdx>=right 가 성립이 되며 반복문이 끝난다.

그리고 if(fIdx>mid)의 else문이 돌아가며 배열의 앞부분에 남은 데이터를 sortArr에 옮기고, 정렬이 끝난다.

성능

우선, 비교연산의 횟수를 알아보자.

그러면, 비교연산의 중심에 있는 문장은 뭘까?

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

        sIdx++;
    }

얘도 말로만 설명하기엔 한계가 있어서, 그림을 첨부하겠다.

그리기도 힘들어서, 윤성우의 열혈 자료구조에 있는 자료를 첨부했다..

위의 그림을 보면, 병합 1단계에서 최대 2회 연산이 된다.

?? 어째서? 8과 2 한번 연산하면 끝이잖아

while문 이후에 있는 if (fidx >= mid) else 이 문장까지 포함해서 그렇다.

그러면, 병합 1단계의 모든 데이터를 진행하면 8회가 된다.

그리고 이후, 병합 2단계에서 2회 + 2회로 최대 4회가 연산이 된다.

그러면, 병합 2단계는 4 x 2 = 8... 이런 식으로 진행이 된다.

1단계에선 8개에 8회. 2단계에선 4개에 4회.

그러면 이 과정을 말로 표현하면..?

정렬의 대상인 데이터 수가 n개 일때, 각 병합의 단계마다 최대 n번의 비교연산 진행

데이터 수가 n개면, 이 n개에 대해서 여기서 진행되는 최대 비교 연산 횟수는

이다.

이 log2n은, "데이터 수가 n개 일 때, 병합 과정이 log2n"만큼 진행되어서, 병합 과정 횟수 k가 log2n이 되기 때문에 그렇다.

이번엔, 이동 연산이다. 얘는 MergeTwoArea에서 while문, if문이 한번 진행될 때 마다 데이터를 이동한다. 그리고 마지막 for문

for (i=left ; i <= tight ; i++) {
        arr[i] = sortArr[i];
}

에서, 임시 배열에 저장된 데이터 전부를 이동한다.

그러면, 데이터 이동이 발생하는 경우는 두가지.

• 임시 배열에 데이터 병합하는 과정에서 한번

• 임시 배열에 저장된 데이터를 원위치로 옮기며 한번

이다.

그러면 앞서 비교 연산횟수의 두배에 해당하는 이동 연산이 이뤄지므로.

2log2n. 하지만 계수는 날리며 앞서 비교연산의 빅-오와 같을 것이다.

배열을 사용한 구현은 임시메모리를 사용한다는 단점이 있었지만, 만약 이 배열이 연결리스트였다면 더욱 좋은 성능을 지녔을 것이다.

오늘은

여기까지