기수 정렬(radix sort)은 값을 비교하지 않는 특이한 정렬이다. 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다.
기수 정렬의 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수이다.
기수 정렬 핵심 이론
기수 정렬은 10개의 큐를 이용한다. 각 큐는 값의 자릿수를 대표한다.
기수 정렬 수행 방식
그림을 보면 원본 배열은 16, 80, 18, 77, 03, 24, 88, 23 이다.
먼저 일의 자릿수 기준으로 배열 원소를 큐에 집어넣는다.
그런 다음 0번째 큐 부터 9번째 큐 까지 pop을 진행한다.
그 결과 80, 03, 23, 24, 16, 77, 18, 88 이 만들어진다.
이어서 십의 자릿수 기준으로 같은 과정을 진행한다.
마지막 자릿수를 기준으로 정렬할 때 까지 앞의 과정을 반복한다.
기수 정렬은 시간 복잡도가 가장 짧은 정렬이다.
만약 코딩 테스트에서 정렬해야 하는 데이터의 개수가 너무 많다면 기수 정렬 알고리즘을 사용해 보자.
- Do it! 알고리즘 코딩테스트 자바 편
