[서울대학교 논자시 준비] 알고리즘 : chapter 4 정렬 - 퀵정렬, 힙정렬

퀵 정렬 수도코드

quickSort(A[], p, r){
if (p<r) then {
	q<- partition(A, p, r); // 분할
    quickSort(A[], p, q-1); // 왼쪽 부분 배열 정렬
    quickSort(A[], q+1, r); // 오른쪽 부분 배열 정렬
}
 
partition(A[], p, r){
	x<- A[r];
    i<-p-1:
    for j<-p to r-1
    	if (A[j]<=x then A[++i]<->A[j];
    A[i+1]<->A[r];
    return i+1;
}

 

퀵 정렬 시간 복잡도

분할은 배열의 왼쪽부터 끝까지 한 번 훑어나가는 작업이기 때문에 O(n) 만큼의 시간이 든다.

퀵 정렬의 수행에서 가장 이상적인 경우는 분할이 항상 반반씩 균등하게 될 때이다. 

이 때 시간 복잡도는 T(n) = T(n/2) + O(n)이 된다.

최악의 경우는 계속해서 한쪽은 하나도 없고 다른쪽에 다 몰리도록 분할이 되는 경우이다.

이 때의 시간 복잡도는 T(n) = T(n-1) + O(n)이 된다.

 

힙정렬

힙은 이진트리로서 맨 아래 층을 제외하고는 완전히 채워져있고 맨 아래층은 왼쪽부터 꽉채워있다

힙은 다음 힙 성질을 만족한다 : 각 노드의 값은 자기 자식의 값보다 작다. 

최소힙과 최대힙

힙을 만드는 함수는 buildHeap, heapify 함수로 동작한다.

 

heapify(A, k, *) 는 A[k]에 매달린 두 서브 트리가 힙 성질을 만족하는 상태에서 A[k]를 루트로 하는 서브 트리 전체가 힙성질을 만족하도록 수선하는 함수이다. 루트 노드 (A[k] 를 제외한 모든 노드가 힙성질을 만족하고 있다고 가정한다)

 

리프 노드는 그 자체로 힙성질을 만족하므로 buildHeap()은 리프가 아닌 노드 중 맨 뒤에서부터 루트로 삼아 heapify()를 수행한다. 

 

힙정렬 수도코드 - 빌드

buildHeap(A[], n){
for i<-rounddown(n/2) down to 1
	heapify(A, i, n);
}

heapify(A[], k, n){
left<-2k;
right<-2k+1;
if (right<=n) then{
	if (A[left]<A[right]) then smaller<-left;
    					else smaller<-right;
}
else if (right<=n) then smaller<-left;
else return;

if (A[smaller]<A[k]) then {
	A[k]<->A[smaller];
    heapify(A, smaller, n);
}
}

힙이 완성되었으면 정렬 작업을 한다. 루트 노드에 있는 원소를 제거해 다른 곳에 저장한다. 루트 노드가 없어졌으므로 트리의 크기가 하나 줄었다. 맨 끝에 있는 원소를 루트 노드로 옮겨 새로운 루트로 삼는다. heapify를 이용해 힙성질을 만족하도록 수선을한다.

 

heapSort(A, n)
{
	buildHeap(A, n);
    for i<-n downto 2{
    	A[1]<->A[i]
        heapify(A, 1, i-1);
       }
 }

힙정렬 수행시간

힙 정렬의 수행시간은 buildHeap()은 O(n)의 시간이 든다. 그리고 for 루프는 n-1번 순환하고 각 순환해서 시간을 좌우하는 heapify는 O(logn)이 드니까 수행시간은 O(nlogn)이다.