정렬은 Comparisons 방식과 Non-Comparisons 방식으로 나뉜다.
아래 구현한 sort 함수들의 base code는 다음과 같다. (merge, quick sort의 경우 약간의 수정이 요구된다.)
비비교 정렬 (Non-Comparison)
Counting Sort
계수 정렬은 각 원소의 개수를 세서 배열에 저장한다. 따라서 원소의 최대값 크기만큼의 배열이 요구된다.
과정
시간복잡도
최선, 평균, 최악의 경우와 관계없이 모두 O(N+K)가 요구된다. K는 원소의 최대값이다. 만약 원소 중 음수가 있다면, 최소값만큼 K를 더해줘야 한다. 즉, N개의 원소에 대해 counting을 한 후, 최소값(or 0) ~ 최대값까지 개수를 저장하는 배열의 값을 탐색해야하는 것이다.
➡️ T(N) = O(N+K)
공간복잡도
K (음수가 있을 경우 최소값+K) 만큼의 추가 배열이 요구된다.
➡️ O(K)
장점
K가 작다면 효율적이다.
단점
K에 따라 시간과 메모리의 낭비가 심할 수 있다.
Radix Sort
기수 정렬은 낮은 자리수부터 비교하여 정렬하는 방식이다. 즉 1의 자리, 10의 자리, 100의 자리, ... 순으로 정렬하여 임시 배열에 저장한다.
과정
시간복잡도
N개의 원소를 최대 자리수만큼 반복하여 정렬하면 된다.
➡️ T(N) = O(N)
공간복잡도
기수의 개수만큼 (eg. 0~9, a~z, A~Z...) 추가적인 공간이 필요하다.
장점
O(N)이라는 매우 빠른 속도로 가능하다.
단점
데이터 타입이 일정해야 한다. 데이터 타입에 따라 구현의 조건이 많아지거나 불가능할 수 있다. (eg. double, float)
양의 정수는 양의 정수끼리, 음의 정수는 음의 정소끼리 비교해야 한다.
추가적인 메모리 공간이 요구된다.
비비교 정렬 알고리즘 비교
| 정렬 | Best | Avg | Worst |
|---|---|---|---|
| Counting | n+k | n+k | n+k |
| Radix | n | n | n |
안정 vs 불안정
Counting, Radix 둘 다 안정 정렬이다.
[참고 사이트]
https://gaemi606.tistory.com/
