기수 정렬

🤔 기수 정렬이란?

• 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다.
• 시간 복잡도는 O(kn)으로, k는 데이터의 자릿수를 의미한다.
• 정렬 알고리즘 중에서 시간 복잡도가 가장 빠른 정렬로, 데이터의 개수가 너무 많으면 기수 정렬을 활용하는 게 유리하다.

👉 기수 정렬 수행 방식

기수 정렬 수행 방식

✔️ 기수 정렬 과정

1. 10개의 큐 리스트를 생성하고, 1의 자릿수 기준으로 큐에 추가한다.
2. 그 다음 첫번째 큐부터 마지막 큐까지 데이터를 pop 연산을 수행한다.
3. 나온 결과를 다시 10의 자릿수를 기준으로 큐에 추가한다.
4. 데이터를 pop 연산하면, 정렬된 데이터로 반환된다.
5. 마지막 자릿수를 기준으로 정렬할 때까지 반복시켜주면 된다.