[ALGO] Lect10. Heap 정렬, Quick-Sort의 알고리즘 및 최선/평균/최악 복잡도

4 minutes to read

강의 정보

강의명: [집콕]인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고
교수: 성균관대학교 소프트웨어학과 허재필 교수님
사이트: http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/course/

이번 시간에는 Heap 정렬, Quick-Sort의 알고리즘 및 최선/평균/최악 복잡도에 대해 배운다.

힙 정렬

주어진 배열을 힙으로 변환하는 방법과, 힙 정렬 알고리즘 구동 원리 및 복잡도 분석에 대해 알아본다.

■ Min Heap Sort

Min Heap의 item을 오름차순으로 정렬하는 방법은 다음과 같다.

주어진 min heap에서 root node의 값을 Pop한다.
재정렬된 min heap에서 root node의 값을 Pop한다.
모든 nodes가 Pop될 때 까지 2번 과정을 반복한다.

위의 알고리즘을 사용하여 Min Heap Sort를 수행할 때, Complexity는 다음과 같다.

\[\sum_{k=1}^{n}{\lg(k)} = \lg(\prod_{k=1}^{n}{k}) = \lg(n!) \approx n\lg(n) \\ ∴ \text{Complexity} = O(n\lg(n))\]

※ Pop operation의 complexity=$O(\lg(n))$ ※

● 문제점

n nodes를 갖는 min heap을 sort하기 위해서는, 기존의 n길이 array 이외에 추가적인 n 길이 array가 필요하다. 즉, 위와 같은 min heap sort 알고리즘은 in-place로 동작하지 않는다.

※ in-place: 추가적인 메모리 공간이 거의 요구되지 않는 특성 ※

Max Heap Sort

위와 같은 (in-place로 동작하지 않는) 문제점을 해결하기 위해 max heap sort 알고리즘을 생각해볼 수 있다.

Heap Sort Algorithm

Heap Sort Algorithm 과정은 다음과 같다.

주어진 Array를 Complete Tree형태로 표현한다.
※ min-heap도 max-heap도 아닌 그냥 binary-tree 형태이다. ※
※ array index=0에서 부터 시작함 (∴ $\text{자식 node}=2k+1 \text{and} 2k+2$; $\text{부모 node}=(k-1)/2$) ※
뒤에서부터 sub-tree별로 max-heap을 만족하도록 재정렬해준다.

Complexity

$\text{depth}=k$인 node의 값이 이동할 수 있는 최대 경로의 길이는 $h-k$와 같으며, depth=k에서 nodes의 개수는 $2^k$개이다. 따라서 최악의 경우 heap sort algorithm을 수행하는 데에 필요한 node의 움직임 수는 다음과 같다.

\[\sum_{k=0}^{h}{2^k(h-k)} = (2^{h+1}-1)-(h+1)\]

이때 node의 개수 $n$에 대해 위 식을 고쳐 쓰면 다음과 같다.

\[n=2^{h+1}-1\text{이므로}\\ \text{complexity}=O{((2^{h+1}-1)-(h+1))}=O(n-\lg(n+1))\\ ∵\ \lg(n+1)=h+1\]

최종적으로 in-place heapify algorithm은 $O(n)$의 복잡도를 갖게 된다.

Max-heap 2 Min-heap

위의 과정을 통해 구한 max-heap을 min-heap으로 변환하는 과정은 다음과 같다.

root node의 값을 Pop한다. (⇒ 마지막 leaf node가 그 자리를 채운 뒤, percolation down된다.)
기존의 leaf node값이 존재하던 자리를 Pop된 값이 채운다.
위 1~2과정을 min-heap이 될 때 까지 반복한다.

■ Complexity

이전에 구했듯 Heapification을 수행하는 데에는 $Θ(n)$이 소요된다 (complete tree→max heap). 이후 max heap을 min heap으로 변환하는 과정에서는 n번의 pop과 insert가 수행되므로 $Θ(n\lg(n))$이 소요된다.
(∵ $\text{pop의 copmlexity}=\lg(n)$ )

Case	Run Time	Comments
Worst	$Θ(n\lg(n))$	No worst case
Average	$Θ(n\lg(n))$
Best	$Θ(n)$	All or most entries are same

퀵 정렬의 평균/최악 복잡도 분석

퀵 정렬 알고리즘 구동 원리 파악 후 평균/최악의 자료 분포 도출 및 각 상황에서의 복잡도를 분석한다.

■ 복습

현재까지 $Θ(n\lg(n))$으로 동작하는 sorting algorithms 두 가지에 대해 알아보았다.

heap sort : in-place에 동작함
merge sort : heap sort보다 빠르지만 in-place에 동작하지 않음

이번에는 in-place에 가까우며 heap sort보다 속도가 빠른 Quick Sort 알고리즘에 대해 알아본다.

Quick Sort

■ 특징

in-place에 가깝다.
평균적으로 Heap Sort Algorithm보다 속도가 빠르다.

Complexity는 다음과 같다.

Case	Time	Memory
Best	$Θ(n\lg(n))$
Average	$Θ(n\lg(n))$	$Θ(\lg(n))$
Worst	$Θ(n^2)$	$Θ(n)$

※ Quick Sort에서는 최대한 데이터의 분포를 worst case가 안되도록 만드는 것이 핵심! ※
※ pivot값을 median값으로 고를 수 있다면 Best Case가 된다. ※
※ pivot값이 최소/최대값이라면 Worst Case가 된다. ⇒ $T(n)=T(n-1)+Θ(n)=Θ(n^2)$ ※

Divide-and-Conquer 방식으로 동작한다.

Merge Sort	Quick Sort
middle point를 기준으로 왼쪽-오른쪽 array로 둘을 나눈다.	특정 값(pivot)을 기준으로 작은 값을 왼쪽, 큰 값을 오른쪽 array에 나눈다 (partitioning).

또한, Merge Sort와 마찬가지로 array size가 굉장히 작은 경우 partitioning을 수행하는 대신에 Insertion Sort와 같은 알고리즘을 수행하는 것이 일반적이다.

Median-of-Three

pivot값으로 median값을 선택하는 경우가 가장 이상적인 Case이다. 일반적으로 Quick Sort에서 median값을 지향하는 pivot 선택 방법은 Median-of-Three 방법이다. Median-of-Three 방법은 다음과 같다.

주어진 Array에서 첫 번째, 마지막, 가운데 위치의 값(총 3개)의 median값을 pivot으로 고른다.
pivot값을 기준으로 partitioning을 한다. ⇒ sub-array 생성
각각의 sub-array에 대해 첫 번째, 마지막, 가운데 위치의 값의 median값을 pivot으로 고른다.
각각의 sub-array에 대해 pivot값을 기준으로 partitioning을 한다.
3~4의 과정을 반복한다.

이때 in-place로 동작하기 위해 다음과 같이 위의 과정이 수행된다.

● partitioning 과정

3개의 값(index=first, middle, last) 중 pivot값(=median)을 구한 뒤 따로 값을 저장한다.
3개의 값 중 최소값은 index first에, 최대값은 index middle 위치에 저장한다.
first에서부터 오른쪽으로 값을 탐색하며 pivot값보다 큰 값을 찾는다.
동시에 last에서부터 왼쪽으로 값을 탐색하며 pivot값보다 작은 값을 찾는다.
pivot값을 기준으로 큰 값과 작은 값이 감지되면 두 값을 swap한다.
두 pointer가 만날 때 까지 3~4번의 과정을 반복한다.
반복 과정이 종료되면 두 개의 pointer 중 더 큰 값을 마지막 array index에 넣고, 빈 자리에 pivot값을 넣어준다.

위의 partitioning과정을 재귀적으로 수행하면 아래와 같이 Quick Sort의 결과를 얻을 수 있다.

Code Implementation

template <typename Type>
void Quicksort(Type *_array, int _first, int _last)
{
    if(_last - _first <= NUM_THRESHOLD)
        Insertion_Sort<Type> (&_array[_first], _last-_first);
    else
    {
        Type pivot = Find_Pivot<Type>(_array, _first, _last);
        int low = _first + 1;
        int high = _last - 2;
        while(_array[low] < pivot) low++;
        while(_array[high] > pivot) high--;
        while(low<high)
        {
            std::swap(_array[low], _array[high]);
            low++;	high--;
            while(_array[low] < pivot) low++;
            while(_array[high] > pivot) high--;
        }
        _array[_last-1] = _array[low];
        _array[low] = pivot;
        Quicksort(_array, _first, low);
        Quicksort(_array, high, _last);
    }
}

Memory Requirement

pivot, start_index, last_index를 stack에 저장해야한다.

따라서 Quicksort의 Memory Requirement는 $Θ(\lg(n))$이다.
한편, Worst-case에서는 memory requirment는 $Θ(n)$가 된다.

Run-time Summary

	Average Run Time	Worst-case Run Time	Average Memory	Worst-case Memory
Heap Sort	$Θ(n\lg(n))$	$Θ(n\lg(n))$	$Θ(1)$	$Θ(1)$
Merge Sort	$Θ(n\lg(n))$	$Θ(n\lg(n))$	$Θ(n)$	$Θ(n)$
Quicksort	$Θ(n\lg(n))$	$Θ(n^2)$	$Θ(\lg(n))$	$Θ(n)$

References

[집콕]인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고-비선형 자료구조, K-MOOC: http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/courseware/1158909c057347478d7386a2b7e97214/e9d736660cad4f76bcb9a05974fe0bf2/1?activate_block_id=block-v1%3ASKKUk%2BSKKU_46%2B2021_T1%2Btype%40vertical%2Bblock%4052b62ff6da2147c9a8a65a6056681d91

Dasol Hong