계수 정렬 (counting sort)과 기수 정렬(radix sort)

계수 정렬은 비교정렬이 아닙니다. 이전까지는 두 수를 비교하여 정렬했다면 이 방법은 단 하나의 비교도 일어나지 않습니다. 그리고 같은 숫자라도 정렬할 때 순서가 섞이지 않는 안정 정렬입니다. 단, 정렬할 때 추가적인 메모리(숫자 개수를 저장할 공간, 결과를 저장할 공간)가 필요하다는 점과, 가장 큰 숫자에 영향을 받는다는 점은 단점입니다. 적은 개수의 숫자를 정렬할 때에는 계수 정렬을 사용하세요. 계수 정렬은 작은 숫자에서는 시간 복잡도가 O(n + k)입니다. k가 정렬할 수들 중에 가장 큰 값을 의미한다. k가 n보다 작은 수이면 O(n)이 되지만, k가 n보다 매우 큰 수이면 O(무한)이 될 수도 있습니다. 예를 들어 10개의 숫자를 정렬하는데, 가장 큰 숫자가 100일 경우, O(n^2)이 됩니다. 방법: 모든 숫자의 개수를 센 후, 누적 합을 구하고, 다시 숫자를 넣어주면 됩니다.
기수정렬: 자리수를 비교해서 정렬하는 방식이다. 단점: 자리수가 없는 것들(부동소수점)은 정렬할 수 없습니다. 문자열과 정수는 거의 다 정렬할 수 있습니다. 시간복잡도: O(dn), d는 가장 큰 데이터의 자리수, 예를 들면 가장 큰 수가 10000이면 자리수가 5니까 O(5n)이 됩니다. 그냥 n이기 때문에 빠릅니다. 같은 두 수가 있어도 순서가 섞이지 않는 안정 정렬입니다. 원리: 자리수 별로 묶어주고, 그것을 실제 배열에 다시 반영하면 됩니다. 단점은 counter과 bucket처럼 추가적인 메모리가 필요하다는 겁니다. 단점을 상쇄할 정도로 빠른 성능을 보여준다.