기수정렬은 값을 비교하지 않는 특이한 정렬입니다
기수정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교합니다
기수정렬의 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를 말합니다
핵심이론
기수정렬은 10개의 큐를 이용합니다
각 큐는 값의 자릿수를 대표합니다
큐가 10개인 이유는 0~9 까지의 숫자를 담기위해서 입니다
각 큐에서는 1의 자릿수부터 기준으로 1의 자릿수의 수가 작은 수부터 순차적으로 큐에 넣어줍니다
이렇게 하는 이유는 10의 자리가 똑같을때 1의 자리 기준으로 작은 수를 먼저 출력하기 위함입니다
그렇다면 만약 숫자가 100의 자리까지 있을 경우에는 위의 10의 자리에서 정렬된 데이터를 바탕으로 100의 자리 기준으로 큐에 넣은 뒤 출력하게 되면 동일한 100의 자리에 대해서는 이미 정렬이 되어있기 때문에 10의 자리 기준 작은 수를 먼저 출력하게 됩니다
이와 같은 과정을 총 자릿수인 k만큼 하는 것이 기수정렬입니다
아래에서 기수정렬이 어떻게 이루어지는지 보겠습니다
시간복잡도
수의 자릿수를 한칸씩 올려서 정렬하는 것이므로
1의 자릿수를 정렬할때 N번의 정렬을 하고
10의 자릿수를 정렬할때 N번의 정렬을 합니다
즉, 각 자릿수(k)에 대해 총 N번 정렬을 하는 것이므로
O(kN)의 시간복잡도를 가지게 됩니다
