Page 263 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

힙 정렬의 시간 복잡도

앞에서 설명한 대로 힙 정렬은 선택 정렬을 응용한 알고리즘입니다. 단순 선택 정렬은 정렬되
지 않은 영역의 모든 요소를 대상으로 가장 큰 값을 선택합니다. 힙 정렬에서는 첫 요소를 꺼
내는 것만으로 가장 큰 값이 구해지므로 첫 요소를 꺼낸 다음 나머지 요소를 다시 힙으로 만들
어야 그 다음에 꺼낼 첫 요소도 가장 큰 값을 유지합니다. 따라서 단순 선택 정렬에서 가장 큰

요소를 선택할 때의 시간 복잡도 O(n)의 값을 한 번에 선택할 수 있어 O(1)로 줄일 수 있습니
다. 그 대신 힙 정렬에서 다시 힙으로 만드는 작업의 시간 복잡도는 O(log n)입니다.
루트를 알맞은 위치로 내리는 작업은 이진 검색과 비슷해 스캔할 때마다 스캔의 범위가 거의 반으로 줄어들기 때문입니다.

따라서 단순 선택 정렬은 전체 정렬에 걸리는 시간 복잡도의 값이 O(n )이지만 힙 정렬은 힙
2
으로 만드는 작업을 요소의 개수만큼 반복하므로 시간 복잡도의 값이 O(n log n)으로 크게
줄어듭니다.

연습 Q21 병합 정렬 알고리즘을 사용해 qsort 함수와 같은 형식으로 호출할 수 있는 다음 함수를 안
문제 정된 정렬이 될 수 있도록 작성하세요.

void m_sort(void *base, size_t nmemb, size_t size,
int(*compar)(const void *, const void *));

Q22 downheap 함수가 호출될 때마다 오른쪽 그림처럼 배열의
10
값을 트리 형식으로 출력하는 프로그램을 작성하세요. ／ ＼
09 05
／ ＼ ／ ＼
08 03 02 04
／＼ ／
06 07 01

실습 6-15 •완성 파일 chap06/heap.c
01 /* 힙 정렬 프로그램 */
02 #include <stdio.h>
03 #include <stdlib.h>
04
05 #define swap (type, x, y) do { type t = x; x = y; y = t; } while(0)
06
07 /*--- a[left] ~ a[right]를 힙으로 만드는 함수 ---*/
08 static void downheap (int a[], int left, int right)
09 {

06•정렬 263