Chap 7. Introduction to Computational Complexity: The Sorting Problem

□Insertion Sort

- 이미 존재하는 정렬된 배열에 값을 삽입하여 정렬하는 알고리즘

 

정렬 방법

1. 첫번째 (i - 1) 배열 자리가 정렬되었고, x가 i번째 자리의 키라고 가정하자

2. x보다 작은 값을 찾을 때까지 x를 S[i - 1], S[i - 2] 등과 비교한다. 이런 자리의 인덱스를 j로 두자.

3. S[j + 1] ~ S[i - 1]의 값을 S[j + 2] ~ S[i]로 이동하고 (j + 1)번째 자리에 x를 삽입한다.

4. 이 과정을 i = 2에서 i = n까지 반복한다.

public static void insertionSort(int n, keyType[]S){
    index i,j;
    keyType x;
    
    for(i = 2; i <= n; i++){
        x = S[i]
        j = i - 1
        while(j > 0 && S[j] > x){
            S[j + 1] = S[j];
            j--;
        }
        S[j + 1] = x;
    }
}

Worst Case Time Complexity

Basic Operation : S[j]와 x의 비교

Input Size : n

 

최악의 시간 복잡도는 배열이 내림차수으로 정렬되어 있을 때 발생한다.

W(n) = ∑(i - 1) = n(n-1) / 2

 

Average Case Time Complexity

 

x를 k번째 자리에 위치할 가능성은 모든 k에 대해서 같으므로 x를 주어진 i에 삽입할 때 필요한 평균 비교 횟수는

[1 + 2 + 3 + ... + (i - 1) + (i - 1)] / i = [i(i - 1)/2 + ( i - 1)] / i = (i + 1) / 2 - 1 / i = (i + 1)/2 - 1/i

A(n) = ∑((i + 1)/2 - 1/i) ≒ (n+4)(n-1)/4 - ln4

□Inversion

- 순서가 반대로 되어 있는 값의 쌍

ex) (5, 8, 2, 6, 4) 에선 6개의 inversions가 존재 -> (5, 2) , (5, 4), (8, 2), (8, 6), (8, 4), (6, 4)

 

Theorem 7.1

값 비교에 의해서만 n개의 개별 값을 정렬하고 각 비교 후 최대 하나의 inversion을 제거하는 모든 알고리즘은 최악의 경우 적어도 n(n-1)/2 번의 값 비교를, 평균적으로는 적어도 n(n- 1)/4 번의 값 비교를 해야한다.

 

Proof of Theorem 7.1

Worst Case인 경우:

순열에 n(n-1)/2개의 inversions가 존재함을 보여주면 된다.

(n, n-1, n-2, ...., 2, 1)이 그런 순열이다. -> 내림차순으로 정렬되어 있기 때문에 2개를 임의로 선택하면 무조건 inversion이다 -> C(n, 2)

 

Average Case인 경우:

주어진 n에 대하여 n!개의 permutations(순열)가 있다.

주어진 순열에 inversions의 평균 수는 알고리즘이 average case에서 계산해야 하는 최소 비교 수이다.

[∑(# of inversions in the i th permutation)] / n!

 

만약 어떤 순열이 k개의 inversions가 있다면, 이 순열의 반전은 C(n, 2) - k 개의 inversions를 갖게 된다. 순열을 반전시키면 inversion이였던 쌍이 순서에 맞게 되고, 순서에 맞던 쌍들이 inversion이 되기 때문이다.

ex) 앞서 봤던 (5, 8, 2, 6, 4) 순열을 다시 보면 6개의 inversions가 있었다. 이 순열을 반전시키면 (4, 6, 2, 8, 5)가 되며, (4, 2), (6, 2), (6, 5), (8, 5)의 4개( = C(5, 2) - 6)의 inversions를 갖게 된다.

 

그래서 모든 순열과 그 반전의 쌍은 C(n, 2)개의 inversions를 갖고, 이런 쌍은 n!/2개 존재하므로 

[∑(# of inversions in the i th permutation)] / n! = [C(n, 2) * n!/2] / n! =  C(n, 2)/2 = n(n - 1)/4

□Heap

- 각 노드에 저장된 값이 자식 노드에 저장된 값보다 크거나 같은 본질적으로 완전한 이진 트리 (heap 속성)

□HeapSort

- 힙이 주어지면 힙 속성을 유지하면서 루트에서 반복적으로 값을 제거한다.
- 제거된 값을 n번째 자리에서 시작하여 첫번째 자리으로 내려가는 배열에 넣는다.

 

해결해야할 것들

1. 어떻게 초기 heap을 구현할 것인가?

2. heap 속성을 유지하면서 어떻게 값을 제거할 것인가?

 

How to construct the initial heap?

1. 배열 S[1 .. n]의 값들이 주어졌을 때, S[1]의 값을 루트 노드로 설정하여 깊이가 d인 완전한 이진 트리를 구현할 수 있다.

 

2. level d인 서브 트리를 heap으로 변환하고, 다음으로 level d-1 서브트리를 heap으로 변환하여 전체 트리가 heap으로 바뀔 때까지 반복해준다.

 

How to remove the root key from a heap?

1. 루트 값을 제거하고 level d의 마지막 값을 루트로 옮긴다.

2. heap 속성이 복원될 때까지 해당 값을 아래로 이동한다.

 

Worst Case Time Complexity of HeapSort

Basic Operation : 값을 아래로 이동하면서 일어나는 값 비교

Input Size : n

makeHeap = n - 1

removeKeys = n lg n - 2n + 2

∴ (n - 1) + (n lg n - 2n + 2) = n lg n - n + 1 𝚯 (n lg n)

□Lower Bounds for Sorting Only by Comparisons of Keys

Decision Tree for insertion sort

a = S[1], b = S[2], c = S[3]이라 가정하자.

Decision Tree를 그려보면 아래와 같이 나온다. 이때, 핑크색으로 적힌 것은 현재 state이다.