10. Heapsort

Heapsort

전략

i. Heapify: N개의 정렬되지 않은 array를 max Heap 구조로 만들기

ii. maximum 키를 순차적으로 pop

 

내림차순 정렬을 위해서는 최대힙, 오름차순 정렬을 위해서는 최소 힙을 만들면 된다.

 

동작

 

i) Heapify

Bottom-up method로 최대 힙을 만들자.

 

이 경우 마지막 Internal node 3-node heap에서 시작한다.

 

 

 

 

 

 

 

이미 T가 루트인 3-node heap은 heap 구조를 만족하므로 패스

 

 

 

 

 

 

 

 

 

 

 

 

 

ii. 순차적으로 maximum key를 지운다.

 

 

 

한 번에 하나씩 최대값을 제거합니다. null을 제거하는 대신 배열에 그대로 두십시오.

 

 

 

 

이런식으로 쭉쭉 하다보면

 

이렇게 정렬이 된다.

 

// 실행 과정

Enter a word to sort: SORTEXAMPLE 

	Unsorted: S O R T E X A M P L E 
	
	N=11 k=5:	S	O	R	T	L	X	A	M	P	E	E 
	N=11 k=4:	S	O	R	T	L	X	A	M	P	E	E 
	N=11 k=3:	S	O	X	T	L	R	A	M	P	E	E 
	N=11 k=2:	S	T	X	P	L	R	A	M	O	E	E 
	N=11 k=1: X T S P L R A M O E E 
	
	Heap ordered: X T S P L R A M O E E				

	N=10 k=1:	T	P	S	O	L	R	A	M	E	E 
	N=9 k=1:	S	P	R	O	L	E	A	M	E 
	N=8 k=1:	R	P	E	O	L	E	A	M 
	N=7 k=1: 	P O E M L E A
	N=6 k=1:	O	M	E	A	L	E 
	N=5 k=1:	M	L	E	A	E 
	N=4 k=1:	L	E	E	A 
	N=3 k=1: 	E A E
	N=2 k=1:	E	A 
	N=1 k=1: 	A
	
	Sorted: A E E	L	M	O	P	R	S	T	X

 

 

// heapify

while (N > 1) {
  swap (a, 1, N--);
  sink (a, 1, N);
}