정렬 알고리즘(Sort Algorithm) (6) - 기수 정렬(Radix Sort)

상위 글 : 정렬 알고리즘(Sort Algorithm)
1. 기수 정렬(Radix Sort)?
기수 정렬은 정수의 자리수의 숫자를 기준으로 큐에 넣어서 순서대로 꺼내는 방식으로 정렬을 기준이 되는 자리수를 바꿔가면서 정렬을 하는 알고리즘입니다.

2. 예시

35

41

55

41

54

49

데이터를 가지고 직접 기수 정렬을 해봅시다.

1. 일의 자리수를 기준으로 각 자리수 큐에 넣는다.

35

31

55

41

54

49

큐

					35
0	1	2	3	4	5	6	7	8	9

35

31

55

41

54

49

큐

	31				35
0	1	2	3	4	5	6	7	8	9

35

31

55

41

54

49

큐

					55
	31				35
0	1	2	3	4	5	6	7	8	9

35

31

55

41

54

49

큐

	41				55
	31				35
0	1	2	3	4	5	6	7	8	9

35

31

55

41

54

49

큐

	41				55
	31			54	35
0	1	2	3	4	5	6	7	8	9

35

31

55

41

54

49

큐

	41				55
	31			54	35				49
0	1	2	3	4	5	6	7	8	9

2. 각 큐에 들어간 원소들을 순서대로 꺼낸다.

31

31

55

41

54

149

큐

	41				55
	31			54	35				49
0	1	2	3	4	5	6	7	8	9

31

41

55

41

54

149

큐

					55
	41			54	35				49
0	1	2	3	4	5	6	7	8	9

31

41

54

41

54

49

큐

					55
				54	35				49
0	1	2	3	4	5	6	7	8	9

31

41

54

35

54

49

큐

					55
					35				49
0	1	2	3	4	5	6	7	8	9

31

41

54

35

55

49

큐

					55				49
0	1	2	3	4	5	6	7	8	9

31

41

54

35

55

49

큐

									49
0	1	2	3	4	5	6	7	8	9

3. 기준이 되는 자리수를 바꿔서 반복한다.

31

41

54

35

55

49

큐

			31
0	1	2	3	4	5	6	7	8	9

31

41

54

35

55

49

큐

			31	41
0	1	2	3	4	5	6	7	8	9

31

41

54

35

55

49

큐

			31	41	54
0	1	2	3	4	5	6	7	8	9

31

41

54

35

55

49

큐

			35
			31	41	54
0	1	2	3	4	5	6	7	8	9

31

41

54

35

55

49

큐

			35		55
			31	41	54
0	1	2	3	4	5	6	7	8	9

31

41

54

35

55

49

큐

			35	49	55
			31	41	54
0	1	2	3	4	5	6	7	8	9

31

41

54

35

55

49

큐

			35	49	55
			31	41	54
0	1	2	3	4	5	6	7	8	9

31

35

54

35

55

49

큐

				49	55
			35	41	54
0	1	2	3	4	5	6	7	8	9

31

35

41

35

55

49

큐

				49	55
				41	54
0	1	2	3	4	5	6	7	8	9

31

35

41

49

55

49

큐

					55
				49	54
0	1	2	3	4	5	6	7	8	9

31

35

41

49

54

49

큐

					55
					54
0	1	2	3	4	5	6	7	8	9

31

35

41

49

54

55

큐

					55
0	1	2	3	4	5	6	7	8	9

31

35

41

49

54

55

3. C를 이용한 구현

다음은 큐를 사용하지 않고, 자릿수 숫자를 세는 방식으로 기수 정렬을 행하는 방식이다.

4. 비트를 이용한 기수 정렬
정수의 자릿수가 아닌 비트 몇개를 단위로 하여 기수 정렬을 행하는 방식으로 정수이외의 경우에도 정렬을 행할 수 있다. 단, 이 경우 HEX코드값에 따라 대소가 구분이 가능한 경우만 가능하다.