정렬 마크다운 도전

힙

힙 순서

key(v) >= ket(parent(v))

힙 높이

$\log{n}$

힙을 이용한 우선 순위 큐 구현

힙 삽입

Alg insertItem(k)

1. advanceLast()
2. z= last
3. Set node z to k
4. expandExternal(z) 
5. upHeap(z)
6 return


Alg upHeap(v)

1. if(isRoot(v))
    return
2. if(key(v) >= key(parent(v)))
    return
3. swapElements(v,parent(v))
4. upHeap(parent(v))

힙 삭제

Alg removeMin()

1. k = key(root())
2. w = last
3. Set root to key(w)
4. retreatLast() - 삭제 후 마지막 노드 갱신
5. z = rightChild(w)
6. reduceExternal(z)
7. downHeap(root())
8. return k


Alg downHeap(v)

1.if(isExternal(leftChild(v))&isExternal(rightChild(v)))
    return
2. smaller = leftChild(v)
3.if(isInternal(rightChild(v)))
    if(key(rightChild(v)) < key(smaller))
        smaller = rightChild(v)
4.if(key(v)<= key(smaller))
    return
5. swapElements(v,smaller)
6. downHeap(smaller)
외부노드면 끝 > 좌우 중 작은 것 찾기 > 그게 나랑 비교해서 크면 바꾸기 > 재귀


Alg reduceExternal(z)

1. w= z.parent
2. zs = sibling(z)
3. if(isRoot(w))
        root = zs
        zs.parent = NULL
    else
        g = w.parent
        zs.parent = g
        if(w == g.left)
            g.left = zs
        else if(w == g.right)
            g.right = zs
4. putnode(z)
5. putnode(w)
6. return zs

마지막 노드 갱신

Alg advancelast
1. 현재 노드가 오른쪽 자식인 동한 부모 노드로 이동한다. 
2. 현재 노드가 왼쪽 자식임녀 형제 노드로 이동한다.
3. 현재 노드가 내부노드인 동안, 왼쪽 자식으로 이동한다.
6시에서 시계 방향으로 돌기

Alg retreatLast
1. 현재 노드가 왼쪽 자식인 동안 부모 노드로 이동한다.
2. 현재 노드가 오른쪽 자식이면 형제 노드로 이동한다.
3. 현재 노드가 내부노드인 동안 오른쪽 자식으로 이동한다.
6시에서 반 시계 방향으로 돌기

힙 성능

힙구현	size ,isEmpty	insertItem, removeMin	minKey, minElement	advanceLast, retreatLast	공간소요
연결	O(1)	O($log{n}$)	O(1)	O($log{n}$)	O(n)
순차	O(1)	O($log{n}$)	O(1)	O(1)	O(n)

힙 정렬

Alg heapSort(L)

1. H = empty heap
2. while(!L.isEmpty())     -phase 1
    k = L.removeFirst()
    H.insertItem(k)
3. while(!H.isempty())     -phase 2
    k = H.removeMin()
    L.addLast(k)
4. return

제자리 힙 정렬

heapSort의 공간 사용을 줄일 수 있다.
여기선 우리가 써왔던 최소힙(루트가 제일 작은 힙)이 아니라 최대힙(루트가 제일 큰 힙)을 사용한다.

Alg inPlaceHeapSort(a)

1. buildHeap(a)           -phase1
2. for i = n downto 2     -phase2
    a[1] swap a[i]
    downHeap(1,i-1)
3. return


Alg buildHeap(a)

1. for i = 1 to n
    insertItem(a[i])
2. return


Alg downHeap(i,last)

1. left = 2i
2. right = 2i+1
3. if(left > last)
    return
4. greater = left
5. if(right<=last)
        if(key(a[right])>key(a[greater]))
            greater = right
6. if(key(a[i])>= key(a[greater]))
    returnm
7. a[i] swap a[greater]
8. downHea(greater,last)

상향식 힙 생성

heapSort의 속도를 높일 수 있다.

재귀적 상향식 힙 생성

Alg buildHeap(l)

1. t = convertToCompleteBinaryTree(l)
2. rBuildHeap(T.root())
3. return t


Alg rBuildheap(v)
if(isInternal(v))
    rbuildHeap(leftChild(v))
    rbuildHeap(rightChild(v))
    downHeap(v)
return

비 재귀적 상향식 힙 생성

Alg buildHeap(a)

1. for i = n/2 downto 1
    downHeap(1,n)
2. return

요약

• 우선순위 큐를 구현하는 또 하나의 방안으로 힙이 있다. 힘은 힙 순서 속성과 완전 이진 트리 속성을 모두 만족하는 이진트리를 할한다.
• n개의 키를 저장한 힙의 높이는$O(\log{n})$이다.
• 힙을 연결 또는 순차 데이터 구조롤 구현할 수 있다. 두가지 구현에 대한 성능은 대부분 작업에서 동일하지만 마지막 노드의 갱신 작업에서는 차이가 있다.
• 힙정렬은 힙을 이용한 정렬이다.
• 힙 정렬은 반복적인 삽입에 의해 힙을 생성하는 1기와 힙으로부터 반복적인 루트 삭제를 통해 정렬을 수행하는 2기로 구성된다. 각 기는 $O(n\log{n})$ 시간에 수행하므로 힙 정렬은 전체적으로 $O(n\log{n})$ 시간에 수행한다.
• 힙 정렬의 기억장소 소요량을 줄이기 위해 제자리에서 수행하도록 구현할 수 있다.
• 재귀적 또는 비재귀적 상향식 힙 생성을 통해 힙 정렬 1기의 수행시간을 $O(n)$ 시간으로 단축할 수 있다.

연습문제

힙 내 최대 키의 위치

적어도 두 개 이상의 키를 저장한 최소힙에 최대 키를 가진 항목이 저장되는 위치는 어디인가? 힙이 유일한 키만 저장하는 경우와 중복 키를 저장하는 경우로 나누어 각각 답하라.

• 아무노드

  중복 허용: 최대키가 중복이면 그 위에 있을 가능성

• 루트를 제외한 아무 노드
• 가장 깊은 내부 노드 가운데 하나
• 외부 노드 바로 위의 내부노드 가운데 하나

  유일키: 최대키가 유일이면 제일 밑에 저장

  힙과 이진트리 순회

  7개의 유일한 원소(1, 2, 3, 4, 5, 6, 7)를 저장하는 힙 T를 다음 방식으로 순회할 경우 T의 원소들이 정렬 순서로 얻어지는 T가 존재할 수 있을까? 있다면 각각의 T의 예를 들어라

• 선위순회 O
• 중위순회 X
• 후위순회 O

합병정렬

분할 통치법

1. 재귀적으로 계속 나눈다.
2. 제일 밑에서 각각에 대한 문제를 재귀적으로 해결한다.
3. 합치면서 각각의 문제를 해결한다.

합병 정렬

Alg mergeSort(l)

1. if(l.size()>1)
    l1, l2 = partition(l,n/2)
    mergeSort(l1)
    mergeSort(l2)
    l = merge(l1,l2)
2. return

합병

Alg merge(l1,l2)

1. l= emptylist
2. while(!l1.isEmpty() && !l2.isEmpty() ){
    if (l1.get(1) <= l2.get(1))
        l.addLast(l1.removeFirst)
    else
        l.addLast(l2.removeFirst)
}
3. while(!l1.Empty)
    l.addLast(l1.removeFirst())
4. while(!l2.Empty)
    l.addLast(l2.removeFirst())
5. return l

점화식

$ T(n) = c$ __ (n<2)
$ T(n) = 2T(n/2) + O(n) $ (n>=2)

배열로 구현한 합병 정렬

Alg mergeSort(a)

1. rMergeSort(A,0,n-1)
2. return


Alg rMergeSort(a,l,r)

1. if(l<r){
    m = (i+r)/2
    rMergeSort(a,l,m)
    rMergeSort(a,m+1,r)
    merge(a,l,m,r)
}
2. return


Alg merge(a,l,m,r)

1. i, k = l
2. j = m+1
3. while(i<=m &&j<=r){
    if (a[i]<= a[j])
        b[k++] = a[i++]
    else
        b[k++] = a[j++]
}
4. while(i<= m)
    b[k++] = a[i++]
5. while(j<= r)
    b[k++] = a[j++]
6. for( k = l to r)
    a[k] = b[k]
7. return

요약

• 분할통치법은 일반적인 알고리즘 설계 기법의 일종이다. 분할통치법에 의한 알고리즘은 분할, 재귀, 통치의 세 단계 해결 과정을 가진다.
• 합병 정렬은 분할통치법에 기초한 정렬 알고리즘이다. 합병 정렬은 힙 정렬처럼, 비교에 기초한 정렬이며 $O(n\log{n})$ 시간에 수행한다. 하지만 힙 정렬과는 달리, 외부의 우선순의 큐를 사용하지 않으며 데이터를 순차적 방식으로 접근한다.
• 두개의 순서 리즈트를 합병하는 merge는 $O(n)$ 시간과 $O(n)$ 공간을 소요한다.

퀵 정렬

Alg quickSort(l)

1. if(l.size()>1){
    k = a position in l
    lt, eq, gt = partition(l,k)
    quickSort(lt)
    quickSort(gt)
    l = merage(lt,eq,gt)
}
2. return

분할

합병정렬에선 merge가 오래걸렸지만 퀵정렬에서는 partition이 오래걸린다.

Alg partition(l,k)

1. p = l.get(k)
2. lt,eq,gt = empty list
3. while(!l.isEmpty()){
    e = l.removeFirst
    if(e<p)
        lt.addLast(e)
    else if(e == p)
        EQ.addLast(e)
    else {e > p}
        gt.addLast(e)
}
4. return lt,eq,gt

제자리 퀵 정렬

Alg inPlaceQuickSort(l,i,r)

1. if(l >= r)
    return
2. k = a position between i and r
3. a, b = inPlacePartition(l,i,r,k)
4. inPlaceQuickSort(l,i,a-1)
5. inPlaceQuickSort(l,b+1,r)


Alg inPlacePartition(l,i,r,k)

1. p = a[k]
2. a[k] = a[r]
3. i = l
4. j = r-1
5. while(i<=j){
    while(i<=j && a[i] <= p )
        i = i+1
    while(j>= i && a[j]>=p)
        j = j-1
    if(i<k)
        a[i] swap a[j]
}
6. a[i] swap a[r]
7. return i

	size ,isEmpty	insertItem, removeMin
기법	분할통치법	분할통치법
실행시간	O($nlog{n}$)최악실행시간	O($n^2$)최악 실행 시간 O($nlog{n}$)기대 실행 시간
분할 vs 합병	분할은 쉽고, 합병은 어렵다.	분할은 어렵고, 합병은 쉽다.
제자리 구현	제자리 합병이 어렵다.	제자리 분할이 쉽다.
실제 작업 순서	작은 것에서 점점 큰 부문제로 진행	큰 것에서 점점 작은 부문제로 진행

요약

• 퀵 정렬은 합병 정렬과 마찬가지로 분할 통치법에 기초한 정렬 알고리즘이다.
• 합병 정렬에서 합병 단계가 시간이 가장 많이 걸리는 단계였는데 비해 퀵 정렬에서는 분할 단계에 가장 많은 시간을 소요한다.
• 퀵 정렬의 최악은 분할 시에 기준원소가 항상 유일한 최소 또는 유일한 최대 원소일 경우다. 이 경우 퀵 정렬의 최악 실행시간은 O($n^2$)이다.
• 무작위 퀵 정렬 버전은 분할 때마다 리스트의 원소 가운데 무작위 원소를 기준원소로 선택합으로써 O($n\log{n}$)기대실행시간을 보장한다.
• 무작위 큌 정렬의 점근적 실행시간은 힙 정렬이나 합병 정렬과 동일하지만, 퀵 정렬이 반복 수행하는 작업의 내용이 비교적 간단한 관계로 실제 수행시간 면에서 위의 두 정렬 알고리즘에 비해 매우 빠르다.

정렬 일반

정렬의 안전성

두 개의 항목 $(k_i,e_i)$와 $(k_j,e_j)$에 대해, $k_i == k_j$이며 i<j일 때 정렬 후에도 $(k_i,e_i)$가 $(k_j,e_j)$보다 앞서 있는 것이 보장된다면 그 정렬 알고리즘을 안정적(stable)이라고 한다.

비교 정렬 알고리즘 비교

	시간	주요 전략	비고
선택 정렬	O($n^2$)	우선 순위 큐 (무순리스트로 구현)	제자리 구현 가능 느림(소규모 입력에 적당) 안정
삽입 정렬	O($n^2$)	우선 순위 큐 (순서리스트로 구현)	제자리 구현 가능 느림(소규모 입력에 적당) 안정
힙 정렬	O($nlog{n}$)	우선 순위 큐 (힙으로 구현)	제자리 구현 가능 빠름(대규모 입력에 적당) 재구성 과정에서 바뀜(불안정)
합병 정렬	O($nlog{n}$)	분할통치	순차 데이터 접근 빠(초대규모 입력에 적당) 안정
퀵 정렬	O($nlog{n}$)기대시간	분할통치	제자리 구현 가능, 무작위 버전 가장 빠름(대규모 입력에 적당) 분할 과정에서 바뀐다 (불안정)

요약

• 입력 리스트ㅡ이 키들을 비교하여 원소들을 키 순서에 따라 재배치하는 방식의 정렬을 비교정렬이라 한다.
• 어떤 비교 정렬 알고리즘이라도 최소 $n\log{n}$ 시간에 수행한다.
• 비교정렬 알고리즘 가운데 힙 정렬, 합병 정렬, 그리고 무작위 버전 퀵 정렬은, 비교정렬의 하한데 수행한다. 이에 비해 선택 정렬, 삽입 정렬, 그리고 결정적 버전 퀵 정렬 알고리즘의 최악의 경우는 비교정렬의 하한에 미치지 못하는 느린 시간에 수행한다.