Sorting
7. Heap Sort
개념
- Heap 자료 구조를 활용한 정렬
- Heap Tree에 모든 자료를 입력한 후 이를 다시 제거해 정렬을 실시
정리
- Unstable & External Sort
- Merge Sort보다 메모리 효율적이며 Quick Sort보다 예상가능한 실행 시간을 가짐
- Quick Sort보다 느릴 수 있지만 보다 안정적이고 예측가능하다는 장점
8. Radix Sort
개념
- 비교 연산 없이 자릿수를 통해 정렬을 실시
- 비교 기반 연산은
O(n * log₂n)보다 빠를 수 없지만 Radix Sort는 가능함
- 연산을 위해 추가적인 메모리 공간을 필요로 함
구현
1자리 숫자만 가진 배열일 경우
- 0~9까지의 배열을 구성한 후, 정렬하려는 배열의 각각의 값을 인덱스로 하는 위치에 값을 저장
- 이후 해당 배열을 그대로 출력하면 정렬된 상태를 유지
(자릿수가 늘어나면 같은 작업을 자릿수별로, 낮은 자릿수부터 실시)
정리
d의 자릿수를 가진 값들을 가진 배열이 n개의 요소를 가질 경우 O(d * n)의 시간 복잡도를 가짐
(일반적으로 d가 n보다 작은 경우가 많으므로 O(n))- 그러나 사용할 수 있는 경우가 제한적; 숫자, 알파벳 등
- Stable & External Sort
9. Counting Sort
개념
- 최댓값이 정해진 요소들에 대해서 사용가능
- 각각의 값이 얼마나 자주 등장했는지를 통해 값을 정렬
- 비교 기반 정렬이 아니므로
O(n + k)의 복잡도를 가지며, 여기서 k는 가능한 값의 범위
구현
- 해당 배열의 최대 값을 찾음
- 최대값을 크기로 하는 배열을 새로 구성
- 이후 주어진 배열에서 각각의 값이 얼마나 자주 등장했는지를 최대값 크기 배열에 입력
- 최대값 크기 배열을 누적된 형태로 연산
- 해당 배열을 기준으로 정렬 실시
정리
- 시간 복잡도와 메모리 공간 모두
O(n + k)
- 범위가 정해진 정수 배열에서 효과적
- Stable & External Sort
k가 n보다 지나치게 큰 경우 메모리 공간 활용이 비효율적일 수 있음(빈 곳이 많아짐)
