정렬 알고리즘의 이론상 성능 한계인 O(nlogn)의 한계를 넘어설 수 있는 현재까지 유일한 알고리즘
길이가 같은 데이터들만 정렬이 가능하다. 정렬 대상 및 기준에 따라서 특정 알고리즘을 적용하여 길이가 다른 데이터들을 정렬할 수도 있다. 이 경우도 매우 제한적이다.
데이터의 가공을 위한 별도의 알고리즘을 고민하고 그에 따른 효율의 문제도 고민한다면 기수 정렬을 사용할 수 있지만 그렇게까지 기수 정렬을 사용할 이유가 별로 없다.
기수(radix)란 주어진 데이터를 구성하는 기본 요소를 의미한다. 예를 들어 2진수의 기수는 0,1이다. 10진수의 기수는 0~9이다.
기수 정렬은 데이터를 구성하는 기본 요소, 즉 기수를 이용해서 정렬을 진행하는 방식
이다.
작은 자릿수에서부터 대소비교를 진행한다.
장점
단점
가장 큰 자릿수에서부터 대소비교를 진행한다.
장점
단점
MSD의 구현 난이도가 LSD보다 상대적으로 높다.
게다가 중간에 데이터를 점검해야 하므로 성능의 이점도 반감될 수 있다.
따라서 LSD 방식의 기수 정렬을 쓴다.
이유
maxLen * num
정렬대상의 수가 n이고, 모든 정렬대상의 길이가 l이라고 할 때, 시간 복잡도에 대한 기수 정렬의 빅-오는 다음과 같다.
O(ln)
기수 정렬은 다른 정렬보다 뛰어난 성능을 보인다. 다만 적용 가능한 대상이 제한적이라는 단점이 있다.