heap sort/counting sort/radix sort

힙 정렬(Heap Sort)

: 힙 자료구조를 이용한 정렬 방법

: 힙에서 항상 가장 큰 원소가 루트노드가 되고 삭제 연산을 수행하면 항상 루트노드의 원소를 삭제하여 반환

힙 정렬 수행 방법

1. 정렬한 원소들을 입력하여 최대 힙 구성

2. 힙에 대하여 삭제 연산을 수행하여 얻은 원소를 마지막 자리에 배치

3. 나머지 원소에 대해서 다시 최대 힙으로 재구성

 (원소의 개수만큼 반복 수행)

정렬되지 않은 [69,10,30,2,16,8,31,22]의 자료들을 힙정렬

-> 정렬할 원소가 8개 이므로 노드가 8개인 완전 이진 트리를 만들고 최대 힙으로 구성

1. 힙에 삭제 연산을 수행하여 루트 노드의 원소 69를 구해서 배열의 마지막 자리에 저장한다. 그리고 나머지 원소들에 대해서 최대 힙으로 재구성

평균 시간복잡도 : O(nlogn)

계수 정렬(Counting Sort)

: 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇개씩 있는지 세는 작업을 하면서 정렬

-속도가 빠르며 안정적이다.

제한사항

1. 정수나 정수로 표현할 수 있는 자료에 대해서만 동작

2. 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야한다.

기수정렬(Radix sort)

:  정수의 자리수의 숫자를 기준으로 큐에 넣어서 순서대로 꺼내는 방식

: 정렬의 기준이 되는 자리수를 바꿔가면서 정렬

35 , 31, 55 ,41 ,54 ,49

1. 일의 자리수를 기준으로 각 자리수 큐에 넣는다.

	41				55
	31			54	35				49
0	1	2	3	4	5	6	7	8	9

2. 각 큐에 들어간 원소들을 순서대로 꺼낸다.

31/41/54/35/55/49

3. 기준이 되는 자리수를 바꿔서 반복한다.

			35	49	55
			31	41	54
0	1	2	3	4	5	6	7	8	9

31 / 35 / 41 / 49 / 54 / 55