기수 정렬(Radix Sort)알고리즘 동작 과정

기수 정렬은 자릿수를 기준으로 정렬하는 알고리즘입니다
실제 데이터 예시를 통해 기수정렬 알고리즘의 동작과정을 살펴보겠습니다

다음과 같은 숫자 배열을 오름차순으로 정렬하겠습니다
[170, 45, 75, 90, 802, 24, 2, 66]

1회차 동작 과정

각 숫자의 1의 자리를 기준으로 0~9까지 버킷에 분류합니다
같은 자리에 들어가는 숫자는 원본 배열의 인덱스 순서를 기준으로 합니다

버킷번호	숫자목록
0	170
1
2	802, 2
3
4	24
5	45, 75
6	66
7
8
9	90

버킷의 숫자를 꺼내서 다시 나열합니다
[170, 802, 2, 24, 45, 75, 66, 90]

2회차 동작 과정

각 숫자의 10의 자리 숫자를 기준으로 0~9까지 버킷에 분류합니다

버킷번호	숫자목록
0	802, 2
1
2	24
3
4	45
5
6	66
7	170, 75
8
9	90

버킷의 숫자를 꺼내서 다시 나열합니다
[802, 2, 24, 45, 66, 170, 75, 90]

3회차 동작 과정

각 숫자의 100의 자리 숫자를 기준으로 0~9까지 버킷에 분류합니다

버킷번호	숫자목록
0	2, 24, 45, 66, 75, 90
1	170
2
3
4
5
6
7
8	802
9

버킷의 숫자를 꺼내서 다시 나열합니다
[2, 24, 45, 66, 75, 90, 170, 802]

이제 원본 배열이 기수 정렬 알고리즘을 통해 오름차순 정렬되었습니다!

정리

기수 정렬(Radix Sort) 알고리즘은 자릿수를 기준으로 정렬하는 알고리즘입니다
10진법인 경우 0~9의 버킷을 만들고
배열의 숫자들 중 최대 자릿수 만큼 반복하여 오름차순 정렬합니다