[ch 10-2] 복잡하지만 효율적인 정렬 알고리즘_3(기수 정렬)

[주제]

- 기수 정렬에 대한 개념

[정의]

- 기수(Radix)란 '주어진 데이터를 구성하는 기본 요소'를 말함

  ※ 예) 2진수의 기수: 0, 1, 10진수의 기수: 0 ~ 9

1. LSD(Least Significant Digit) 방식의 정렬

- '가장 작은 자릿수'부터 정렬을 진행

  ※ 가장 오른쪽부터(숫자로 치면 1의 자리수부터)

- 가장 작은 자릿수부터 가장 큰 자릿수까지 비교해야 된다는 단점이 존재하지만, 코드 구현은 MSD에 비해 간결

2. MSD(Most Significant Digit) 방식의 정렬

- '가장 큰 자릿수'부터 정렬을 진행

  ※ 가장 왼쪽부터

- 코드 구현은 LSD에 비해 추가 작업(정렬 상태 확인)이 필요하지만, 중간에 정렬이 완료될 수 있는 장점이 존재

[중요]

- 기수 정렬은 정렬 순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않음

- 정렬 대상의 모든 길이가 동일해야 가장 효율적

  ※ 좋은 예) [123, 486, 309, 944], [blue, rice, pain, book] 등등

  ※ 나쁜 예) [5643, -43, 1, 87912], [sky, pencil, water, a] 등등

- 길이가 각각 다를경우 빈 공간을 메꿔야하는 추가 작업 발생 → 성능 저하

- 정렬 대상의 자리수를 기준으로 '버킷'이라는 공간에 '큐(Queue)' 방식으로 저장 후 다시 꺼냄

■ 그림(기수 정렬 과정)

- 숫자 '7, 5, 3, 9'를 오름차순으로 정렬

- 정렬할 숫자들을 '버킷' 공간에 각 숫자와 동일한 위치에 저장

- '버킷' 공간에 저장된 숫자들을 처음부터 다시 꺼내어 정렬 공간에 차례대로 저장

  ※ 버킷 공간의 크기는 숫자 길이와 동일

■ 그림(LSD 정렬 과정)

- 숫자 '134, 224, 232, 122'를 오름차순으로 정렬

- '1'의 자리수부터 버킷에 저장 시작

- 버킷 공간에 각 숫자에 맞게 저장

- 위치가 같을 경우 순서대로 저장

- 꺼낼 때는 먼저 저장된 숫자부터 꺼냄

- 1차 정렬된 숫자들을 '10'의 자리수부터 버킷에 저장 시작

- 위와 동일하게 진행

- 2차 정렬된 숫자들을 '100'의 자리수부터 버킷에 저장 시작

- 가장 큰 자리수까지 정렬 완료

■ 그림(MSD 정렬 과정)

- '100'의 자리수부터 버킷에 저장 시작

- 이후 진행 방식 동일

- 두 번째부터는 1차 정렬된 숫자들을 그룹으로 분류

- '100'의 자리수가 동일한 것끼리 그룹

  ※ (134, 122), (224, 232)

- 각 그룹별로 따로 정렬을 진행

- 두 번째 그룹은 정렬할 마지막(1의 자리수)을 비교하지 않아도 이전에 정렬이 완료된 상태이므로 더 이상 정렬을 진행하지 않음