복잡하지만 효율적인 정렬 알고리즘(14)

10-2. 복잡하지만 효율적인 정렬 알고리즘 ⑭

이번시간에는 기수정렬에 대해 배워보자.

기수정렬은 학문적 차원에서 알아두면 좋을 정렬이다. 기수정렬의 특징부터 알려주겠다.

기수정렬의 특징 3가지

1. 정렬 순서의 앞서고 뒤섬을 비교하지 않는다.

기존의 정렬들은 ‘비교’를 통해 데이터들의 자리를 찾아가는 과정의 연속이었다. 그래서 대부분 정렬 알고리즘의 핵심 연산은 비교연산이었다.

그런데 기수정렬은 정렬하는데 비교를 하지 않는다고 함. how??

1. 정렬알고리즘의 한계로 알려진 $O(nlog_2n)$을 뛰어넘을 수 있다.

일반적으로 알려진 바는.. 정렬 알고리즘이 위의 빅오를 뛰어넘기 위해서는 다른 손해를 감수해야한다고 한다. 그런데 이 알고리즘을 거의 유일하게 뛰어넘는 성능을 보이는 알고리즘이 기수정렬이다.

그럼 기수정렬은 정렬 알고리즘 아닌가? 라는 질문이 당연히 든다. 맞다. 기수정렬이 바로 그 손해를 감수하는 알고리즘이다.

1. 적용할 수 있는 대상이 매우 제한적이다. 기수정렬은 길이가 동일한 데이터의 정렬에만 용이하다.

하지만 제한적인 범위내의 데이터 정렬에서는 매우 뛰어난 성능을 보이는 정렬알고리즘이 기수정렬이다.

이제 기수정렬이 적용가능한 범위에 대해 이야기해보자.

위와 같은 경우는 어떤 순서로도 기수정렬이 가능하다.