[정렬] 기수 정렬

✔ 기수 정렬

기수 정렬이란?

• 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식
• 값을 비교하지 않는 특이한 정렬
• 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교
• 10개의 큐를 이용하며, 각 큐는 값의 자릿수를 대표함 (0 ~ 9)
• 시간 복잡도는 O(kN)으로, 여기서 k는 데이터의 자릿수
• 시간 복잡도가 가장 짧은 정렬이므로, 정렬해야 하는 데이터의 개수가 너무 많을 시 사용

기수 정렬 과정

1. 일의 자릿수를 기준으로 배열 원소를 큐에 집어넣음
2. 0번째 큐부터 9번째 큐까지 pop을 진행하여 일의 자릿수를 기준으로 정렬된 데이터를 꺼냄
3. 이어서 십의 자릿수를 기준으로 같은 과정을 진행
   • 십의 자릿수에서 같은 자릿수일 때, 일의 자릿수가 더 작은 데이터가 큐에 먼저 들어가게 되어 오름차순 정렬이 가능해짐
4. 마지막 자릿수를 기준으로 정렬할 때까지 앞의 과정을 반복

 

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn