정렬 문제

🐽 버블 정렬 알고리즘

• 인접한 두 원소를 검사하여 정렬
• 문제: 비내림차순으로 n개의 키 정렬
• 입력: 양의 정수 n, 키의 배열 S[1..n]
• 출력: 비내림차순으로 정렬된 키의 배열 S[1..n]

의사코드

void bubbleSort(int n, keytype &S[]) {
    index i, j;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n-i; j++) {
            if(S[j] > S[j+1])
                swap S[j] and S[j+1];
        }
    }
}

• 큰 수일 경우 한 칸씩 뒤로

버블 정렬 분석 - 모든 경우

• 단위 연산: 비교

i	j	횟수
1	1..	n-1
2	1..	n-2
…
n	1..	0

• $T(n) = \frac{n(n-1)}{2}$

🐽 삽입 정렬 알고리즘

• 이미 정렬된 배열에 항목을 끼워 넣음으로써 정렬하는 알고리즘
• 문제: 비내림차순으로 n개의 키 정렬
• 입력: 양의 정수 n, 키의 배열 S[1..n]
• 출력: 비내림차순으로 정렬된 키의 배열 S[1..n]

의사코드

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

삽입 정렬 분석 - 최악의 경우

• 기본 연산: 비교
• i가 주어졌을 때, while loop에서 최대 i-1번의 비교 이루어짐
• $W(n) = \sum_{i=2}^{n} (i-1) = \frac{n(n-1)}{2}$

평균의 경우

• i가 주어졌을 때 x가 삽입될 수 있는 장소: i개

삽입할 장소의 인덱스	비교 횟수
i	1
i-1	2
…	…
2	i-1
1	i-1

• x를 삽입하는데 필요한 비교 횟수
  $1\frac{1}{i} + 2\frac{1}{i} + … + (i-1)\frac{1}{i} + (i-1)\frac{1}{i} = \frac{1}{i} \sum_{k=1}^{i-1} k + \frac{i-1}{i} = \frac{(i-1)i}{2i} + \frac{i-1}{i} = \frac{i+1}{2} - \frac{1}{i}$

• 정렬에 필요한 평균 비교 횟수
  $\sum_{i=2}^{n} (\frac{i+1}{2} - \frac{1}{i}) ≈ \frac{(n+4)(n-1)}{4} - ln^n ≈ \frac{n^2}{4} ∈ Θ(n^2)$

🐤 교환 정렬 알고리즘

• 문제: n개의 수로 구성된 배열 S 오름차순 정렬
• 입력: 양의 정수 n, 배열 S
• 출력: 오름차순으로 정렬된 배열 S

의사코드

void exchangeSort(int n, number S[]) {
    index i, j;
    for(i = 1; i <= n; i++) {
        for(j = i+1; j <= n; j++)
            if(S[j] < S[i]) swap S[i] and S[j];
    }
}

swap(index i, j, number &S[]) {
    number temp;
    temp = S[i];
    S[i] = S[j];
    S[j] = temp;
}

시간복잡도

• 단위 연산: 조건문 (S[j], S[i] 비교)
• 모든 경우 분석
  • j-loop가 수행될 때마다 조건문 1번씩 수행
  • 조건문 총 수행 횟수
    • i=1, 2, 3, .., n-1 에 따라
    • j-loop n-1, n-2, n-3, …, 1 번 수행
  • $T(n) = (n-1) + (n-2) + … + 1 = \frac{(n-1)n}{2}$
• 최악의 경우
  • 기본 연산: 할당
  • 1번 교환하는데 3번 지정
  • $W(n) = 3(n-1) + 3(n-2) + … + 3 = \frac{3n(n-1)}{2}$
• 평균의 경우
  • 기본 연산: 할당
  • i와 j를 비교했을 때 i가 클 확률은 $\frac{1}{2}$, i가 클 때 지정이 발생하므로
  • 지정의 횟수: $\frac{3(n-1)}{2}$
  • $A(n) = \frac{3(n-1)}{2} + \frac{3(n-2)}{2} + … + \frac{3}{2} = \frac{3n(n-1)}{4}$

🐽 선택 정렬 알고리즘

• 문제: 비내림차순으로 n개의 키 정렬
• 입력: 양의 정수 n, 키의 배열 S[1..n]
• 출력; 비내림차순으로 정렬된 키의 배열 S[1..n]

의사코드

void selectionSort(int n, keytype S[]) {
    index i, j, smallest;
    for(i = 1; i <= n-1; i++) {
        smallest = i;
        for(j = i+1; j <= n; j++) {
            if(S[j] < S[smallest])   // 기본연산: 비교
                smallest = j;
        }
        exchange S[i] and S[smallest];   // 할당
    }
}

exchange(index i, j, number &S[]) {
    number temp;
    temp = S[i];
    S[i] = S[j];
    S[j] = temp;
}

선택 정렬 분석 - 모든 경우

• 기본 연산: 비교

i	횟수
1	n-1
2	n-2
…
n-1	1

• 비교 횟수의 합: $\frac{n(n-1)}{2}$
• $T(n) = \frac{n^2}{2}$

• 기본 연산: 할당
  • 1번 교환하는데 3번 지정
• $T(n) = 3(n-1)$

🐽 힙 정렬

최대 힙 Max Heap

• 최대 트리
  • 이진 트리에서 각 노드의 키 값이 그 자식 노드보다 큰 트리
• 최대 힙
  • 최대 트리이면서 완전 이진 트리
  • 최대 트리에서 루트는 가장 큰 키 값을 가짐
  • 각 노드의 키 값은 그 노드의 자식 노드에 저장된 값보다 크거나 같음

• 삽입 연산
  • 완전 이진 트리의 조건을 만족하기 위해 새 노드는 트리의 마지막 위치에 삽입
  • 최대 트리 조건을 만족하기 위해 새 노드는 상위 노드와 반복적으로 비교하여 알맞은 위치 찾음
    

• 삭제 연산
  • 최대 힙에서의 삭제는 루트 노드의 삭제
  • 루트 노드를 return
  • 가장 마지막 노드를 루트로 가져와서 최대 힙의 특성을 만족하도록 제 위치를 찾아줌 shiftdown
    

힙 정렬을 위한 데이터 구조

• shiftdown: 힙의 특성을 만족하도록 키 값을 아래로 내리는 연산
• root: 루트 키를 return하고, 바닥 노드를 루트로 옮겨 shiftdown하여 힙을 복원함 (삭제 연산)
• removekeys: 힙의 키를 정렬된 순서로 배열에 위치시키는 알고리즘
• makeheap: 본질적으로 완전한 이진 트리를 힙 트리로 구성

shiftdown()

• 힙 구조 특성 만족하도록 구성

void shiftdown(heap& H, index i) {    // i는 노드 번호
    index parent, largerchild;
    keytype shiftkey;
    bool spotfound;
    shiftkey = H.S[i];
    parent = i;
    spotfound = false;
    while(2*parent <= H.heapsize && !spotfound) {  // 자식 노드가 하나라도 있으면
        // 자식 노드가 2개라면, 왼쪽/오른쪽 중 어느 자식 노드가 더 큰지 판별
        if(2*parent < H.heapsize && H.S[2*parent] < H.S[2*parent+1])   
            largerchild = 2*parent + 1;   // 오른쪽
        else largerchild = 2*parent;      // 왼쪽

        if(shiftkey < H.S[largerchild]) {
            H.S[parent] = H.S[largerchild];
            parent = largerchild;
        }
        else spotfound = true;
    }
    H.S[parent] = shiftkey;
}

struct heap{
    keytype S[1..n];
    int heapsize;
};

• 자식 노드 index: 적어도 부모 노드의 2배

makeheap()

• 힙 구조 구성

void makeheap(int n, heap& H) {
    index i;
    H.heapsize = n;
    for(i = ⌊n/2⌋; i >= 1; i--) 
        shiftdown(H, i);
}

root()

• 힙 구조의 루트 값 얻기 & 힙 복원

keytype root(heap& H) {
    keytype keyout;
    keyout = H.S[1];
    H.S[1] = H.S[heapsize];      // 가장 마지막 노드를 루트로
    H.heapsize = H.heapsize - 1;
    shiftdown(H, 1);             // 힙 트리 특성 만족하도록 구성
    return keyout;
}

removekeys()

• 정렬
• 힙 구조의 루트를 배열로 이동

void removekeys(int n, heap H, keytype S[]) {
    index i;
    for(i = n; i >= 1; i--)
        S[i] = root(H);
}

힙 정렬 알고리즘

void heapSort(int n, heap& H, keytype S[]) {
    makeheap(n, H);        // shiftdown()
    removeheap(n, H, S);   // shiftdown()
}

• makeheap과 removekeys 모두 shiftdown 호출하므로 따로 분석

makeheap 시간복잡도 - 최악의 경우

• 단위 연산: shiftdown 프로시저에서의 키 비교
• $n = 2^k (= 2^d)$라 가정

depth	node 수	키가 shift되는 최대 횟수
0	$2^0$	d-1
1	$2^1$	d-2
..	..	..
j	$2^j$	d-j-1
..	..	..
d-2	$2^{d-2}$	1
d-1	$2^{d-1}$	0

• 최대 횟수의 합
  $\sum_{j=0}^{d-1} 2^j (d-j-1)$
  = $2^d - d - 1$

• 깊이가 d인 경우 shiftdown 될 횟수의 상한값인 d를 더하면 $2^d - 1$이 됨
• 한 번 shiftdown될 때마다 2번씩 비교
• 실제 비교 횟수: $2(n-1)$

removekeys 시간복잡도 - 최악의 경우

• $n = 2^k (= 2^d)$라 가정
• 총 shift 횟수: $\sum_{j=0}^{d-1} j2^j = nlg^n - 2n + 2$
• 한 번 shift될 때마다 2번씩 비교하므로 실제 비교 횟수: $2nlg^n - 4n + 4$
• 따라서, 최악의 경우: $W(n) ∈ Θ(nlg^n)$

힙 정렬 시간복잡도

• makeheap 시간복잡도 + removekeys 시간복잡도
• 최악의 경우: $W(n) ∈ Θ(nlg^n)$

🐽 기수 정렬 RADIX

• d 개의 숫자로 표현한 k진법 체계의 수를 키로 표현하여 각 숫자에 따라 키를 분배하는 방식

각 키의 가장 왼쪽 숫자부터 기준으로 삼는 경우

오른쪽 숫자부터 분배의 기준으로 삼는 경우

의사코드

void radixsort(node_pointer& masterlist, int numdigits) {
    // globally node_pointer list[0.9];
    index i;
    for(i = 1; i <= numdigits; i++) {
        distribute(masterlist, i);
        coalesce(masterlist);
    }
}

void distribute(node_pointer& masterlist, index i) {
    index j;
    node_pointer p;
    for(j = 0; j <= 9; j++) {
        list[j] = NULL;
    }
    p = masterlist;
    while(p != NULL) {
        j = p -> key에서 오른쪽으로부터 i번째 숫자값;
        p를 list[j]의 끝에 링크;
        p = p -> link;
    }       
}

void coalesce(node_pointer& masterlist) {
    index j;
    masterlist = NULL;
    for(j = 0; j <= 9; j++)
        list[j]에 있는 마디들을 masterlist의 끝에 링크;
}

기수 정렬 알고리즘 분석 - 모든 경우

• 단위 연산: 뭉치에 수를 추가하는 연산 (링크 연산)
• 입력 크기: 정렬하는 정수 개수 n, 각 정수를 이루는 digit의 최대 개수 numdigits
• 모든 경우 시간복잡도
  $T(n) = numdigits(n + 10) ∈ Θ(numdigits * n)$