🚩 기수정렬? > 기수 정렬은 전체 값을 비교하지 않는 특이한 정렬로, 두 값을 놓고 비교할 때 자릿수에 있는 데이터를 비교한다. 기수정렬의 시간복잡도는 O(kn)인데, 여기서 k는 데이터의 자릿수를 말한다. 즉, 데이터의 자릿수가 많지 않으면서 데이터 수는 많을 경우 기수정렬을 활용하는 것이 효과적이라고 할 수 있다. 기수정렬의 핵심 이론 기수정렬은 10개의 큐를 이용한다. 여기서 각 큐는 자릿수를 대표하는데, 각 자릿수가 0~9까지 10개이기 때문에 10개의 큐를 이용하는 것이다. 다음과 같은 데이터가 있다고 하자. [16 80 18 77 03 24 80 23] 일의 자릿수를 기준으로 데이터를 큐에 저장했을 때 다음과 같다. 802477 1의 자리를 기준으로 해당 데이터들은 정렬되어있는 것을 알 수 있다. 이제 일의 자릿수가 정렬된 데이터들을 가지고, 10의 자리를 기준으로 큐에 저장해보자.