[정렬 알고리즘] - 기수 정렬 O(kn)

기수정렬 (Radix Sort)

직접 값을 비교하지 않는 특이한 정렬로, 각 값에 비교할 자릿수를 정한 뒤 자릿수끼리 비교한다.

O(kn)의 시간복잡도를 갖는다 (k는 자릿수)

 

핵심 이론

각 자릿수에는 0~9 10개의 데이터를 받을 수 있으므로 10개의 Queue를 이용한다.

각 Queue는 각 자릿수를 대표한다.

대상 데이터의 각 자릿수별로 해당하는 숫자의 큐에 저장한 뒤 POP 한다.

 

1의 자리 기수 Queue 보관 → POP

10의 자리 기수 Queue 보관 → POP

 

 

 

[1의 자리 정렬]

16

80

18

77

03

24

88

23

데이터	16	80	18	77	03	24	88	23
1의 자리	1(6)	8(0)	1(8)	7(7)	0(3)	2(4)	8(8)	2(3)
기수	6	0	8	7	3	4	8	3

 

데이터	80			23 03	24		16	77	88 18
큐	0	1	2	3	4	5	6	7	8	9

 

POP (Queue 자료구조 이므로 FIFO 형태로 POP추출)

80

03

23

24

16

77

18

88

 

비교횟수 N번

 

[10의 자리 정렬]

데이터	80	03	23	24	16	77	18	88
10의 자리	(8)0	(0)3	(2)3	(2)4	(1)6	(7)7	(1)8	(8)8
기수	8	0	2	2	1	7	1	8

 

데이터	03	18 16	24 23					77	88 80
큐	0	1	2	3	4	5	6	7	8	9

 

POP (Queue 자료구조 이므로 FIFO 형태로 POP추출)

03

16

18

23

24

77

80

88

 

비교횟수 N번

 

 

시간복잡도 N * 2 = 2N

N :데이터갯수 8

2 : 자릿수 K

즉, 자릿수 * 데이터갯수인 O(kn)의 시간복잡도를 갖게 된다.

 

각 자릿수별 정렬 이유

• 1의자리 정렬
  10의자리가 동일할 때 1의자리가 더 작은 애가 먼저 나열되게 끔 하기위한 정렬 작업
• 10의자리 정렬
  100의 자리가 동일할 때 10의자리가 더 작은 애가 먼저 나열되게 끔 하기 위한 정렬 작업
• 100의자리 정렬
  1000의 자리가 동일할 때 100의자리가 더 작은 애가 먼저 나열되게 끔 하기 위한 정렬 작업

 

프로그래밍 언어로 구현하기 위해

• 각 데이터의 기수를 관리할 Queue라는 공간을 구현해야 한다.
• 몇자리인지 파악하는 로직이 필요하다.