알고리즘 개념[기초] - 기수 정렬

오늘은 기수 정렬에 대한 개념을 익혀보도록 하겠습니다.

기수 정렬은 값을 비교하지 않는 특이한 정렬입니다. 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교합니다.

시간 복잡도 : O(kn) - k : 데이터의 자릿수

기수 정렬의 핵심이론은 10개의 큐를 이용한다는 점입니다. 일반적으로 10진수의 모든 숫자는 0~9의 숫자로 구성되어 있습니다.

대상 데이터를 자릿수마다 해당하는 데이터를 저장하기 위해서 10개의 큐를 사용하는 것입니다.

기수정렬 수행 과정은 다음과 같습니다.
1. 일의 자릿수 기준으로 배열 요소를 큐에 담습니다.(add)
2. 이 후에 0부터 9번째 큐까지 pop을 진행하여 배열에 담습니다.
3. 그 다음 십의 자릿수를 기준으로 같은 과정을 진행합니다.
4. 마지막 자릿수를 기준으로 정렬할 때까지 앞의 과정을 반복합니다.

기수정렬은 시간 복잡도가 가장 짧은 정렬 방식입니다. 따라서 정렬할 데이터의 갯수가 너무 많으면 기수 정렬 알고리즘을 활요하세요!