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