04 정렬 (2)

힙 정렬 (Heap Sort)

buildHeap(A[], n)
{
	for i ← n/2 downto 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 (left ≤ n) then smaller ← left;
	else return;
	if (A[smaller] < A[k]) then {
		A[k] ↔ A[smaller];
		heapify(A, smaller, n);
	}
}

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

힙 정렬의 수행시간은 $O(nlogn)$

 

 

+) 비교 연산을 기본으로 하는 정렬은 시간 복잡도가 최소 $\Omega(nlogn)$이다.

하지만 원소들이 특수한 성질을 만족하면 $O(n)$도 가능하다.

 

기수 정렬 (Radix Sort)

입력이 모두 k 자릿수 이하의 자연수인 특수한 경우에 사용가능

radixSort(A[], n, k)
{
	for i ← 1 to k
		i번째 자릿수에 대해 A[1…n]을 안정성을 유지하면서 정렬;
}

안정성을 유지하면서 '정렬'할때,

0부터 9까지 표시된 10개의 공간을 준비해놓고 원소를 해당 공간에 차례대로 넣어주는 등의 방법을 사용

시간복잡도는 $O(n)$

 

계수 정렬 (Counting Sort)

원소들의 값이 $O(n)$을 넘지 않는 경우에 사용가능

countingSort(A[], B[], n)
{
	for i ← 1 to k
		C[i] ← 0;
	for j ← 1 to n
		C[A[j]]++;
	for i ← 2 to k
		C[i] ← C[i] + C[i-1];
	for j ← n downto 1 {
		B[C[A[j]]] ← A[j];
		C[A[j]]--;
	}
}

계수 정렬의 수행시간은 $\Theta(n)$인데 그 이유는 다음과 같다.

첫번째 for loop는 $\Theta(k)$

두번째 for loop는 $\Theta(n)$

세번째 for loop는 $\Theta(k)$

네번째 for loop는 $\Theta(n)$

따라서, k가 $O(n)$이면 총 시간은 $\Theta(n)$