4. 정렬 (3) - 힙, 기수 정렬

1. 힙 정렬 (Heap sort)

 

- 합 정렬은 대표적인 우선순위 큐인 힙 자료구조를 사용하는 정렬 알고리즘이다.

-지금까지 소개한 정렬 알고리즘들이 모두 주어진 배열 자료구조 위에서 정렬한 것에 반해, 힙 정렬은 힙 자료구조를 사용해서 정렬

 

-[힙의 정의]

-힙은 다음 두 조건을 만족해야 한다 : 완전 이진 트리 구조를 사용해야 한다, 모든 노드는 값을 갖고, 자식 노드 값보다 크거나 같다.

-조건들을 만족하면 우선순위가 가장 큰 원소가 루트에 자리하게 된다

 

-[힙의 구성]

-

 

 

2. 기수 정렬

-기수 정렬(Radix Sort)는 원소들이 모두 상수 k개 이하의 자릿수를 가진 자연수와 같은 특수한 경우에 (자연수가 아닌 제한된 길이를 가진 알파벳 등도 해당함) 사용 가능한 알고리즘이다.

-우선 가장 낮은 자릿수만으로 모든 수를 재배열한다 (정렬)

-다음으로 둘째 자릿수를 대상으로 정렬한다.

-이어서 셋째 자리수에 대해, 마지막으로 넷째 자리수에 대해 정렬하면 작업이 마무리된다.

-정렬할 때 같은 값이면, 앞의 순서를 유지해 주어야 하는데, 이를 안정성을 유지하는 정렬 (Stable Sort) 라고 한다.

-여기서 '안정성을 유지한다'라는 사실이 매우 중요한데, 이것은 값이 같은 원소끼리는 정렬 후에 원래의 순서가 바뀌지 않는 성질을 의미한다.

 

-하나의 자릿수를 정렬하는데 앞에서 배운 정렬 알고리즘 중 하나를 사용하면 이미 O(n)의 시간을 초과하므로 다른 방법을 사용해야한다.

-예를 들어, 0부터 9까지 표시된 10개의 리스트를 준비하고 각각의 수를 가진 입력은 해당 리스트에 차례대로 넣어주는 방법을 사용해 이 부분을 O(n)에 처리가 가능하다. 

-이 부분을 O(n)에 끝낼 수 있다면 알고리즘은 이를 k번 반복하므로 시간은 O(kn)이 된다.

-이 때 k가 상수라면 기수 정렬의 수행 시간은 O(n)이 되믐로, k가 상수가 아니라면 기수정렬은 매력이 없다.

 

-기수 정렬 참고 페이지 : 06 정렬 알고리즘 - 기수 정렬(Radix Sort) (tistory.com)