기수 정렬(Radix Sort) 의 개념

기수 정렬은 데이터를 개별 자리수 단위로 정렬하여 데이터를 정렬하는 방식입니다. 주어진 데이터의 값을 자릿수별로 나누고, 각 자릿수에 대해 계수 정렬과 같은 안정적인 정렬 알고리즘을 적용해 정렬하는 방법입니다.

계수 정렬에 대해 알고 싶으신 분들은, 아래의 글을 참고하세요!

[Algorithm] – “계수 정렬(Counting Sort)”

기수 정렬은 어떤 자리부터 정렬을 진행하느냐에 따라 LSD 기수 정렬, MSD 기수 정렬 로 구분할 수 있습니다.

• LSD 기수 정렬은 낮은 자리부터 높은 자리로 정렬을 진행합니다.
• MSD 기수 정렬은 높은 자리부터 낮은 자리로 정렬을 진행합니다.

LSD 기수 정렬

LSD 기수 정렬 방식으로 아래의 배열을 정렬해 봅시다.

arr = [288, 265, 482, 095, 361, 068, 185, 100]

LSD 기수 정렬은 낮은 자리부터 높은 자리로 정렬을 진행한다고 했습니다. 입력은 각각 세 자리 숫자입니다. 그리고, 가장 낮은 자리인 일의 자리는 [8, 5, 2, 5, 1, 8, 5, 0] 입니다. 이 일의 자리 숫자를 기준으로 정렬을 하면, 아래와 같은 모양새가 됩니다.

arr = [288, 265, 482, 095, 361, 068, 185, 100]

# 일의 자리 숫자로 정렬 ..
# 일의 자리 숫자 기준, [0, 1, 2, 5, 5, 5, 8, 8]
arr = [100, 361, 482, 265, 095, 185, 288, 068]

위에서 기수 정렬은 각 자릿수에 대해서 안정적인 정렬 알고리즘을 적용한다고 했죠? 어떤 알고리즘의 정렬이 안정적이라는 것은 같은 값을 가진 데이터가 있을 때, 정렬 후에도 그것들의 상대적인 위치가 유지된다는 의미입니다. 예컨대 위의 경우, 265, 095, 185 는 모두 같은 일의 자리 숫자를 가집니다. 그리고 각 자리 숫자에 안정적인 정렬 알고리즘을 적용했기 때문에, 정렬 후에도 상대적인 위치가 유지되도록 265, 095, 185 의 순서대로 정렬됩니다.

arr = [288, 265, 482, 095, 361, 068, 185, 100]

# 일의 자리 숫자로 정렬 ..
# 일의 자리 숫자 기준, [0, 1, 2, 5, 5, 5, 8, 8]
arr = [100, 361, 482, 265, 095, 185, 288, 068]

# 십의 자리 숫자로 정렬..
# 십의 자리 숫자 기준 0, 6, 8, 6, 9, 8, 8, 6
arr = [100, 361, 265, 068, 482, 185, 288, 095]

# 백의 자리 숫자로 정렬..
# 백의 자리 숫자 기준 1, 3, 2, 0, 4, 1, 2, 0
arr = [068, 095, 100, 185, 265, 288, 361, 482]

마찬가지로, 이제 십의 자리 숫자, 백의 자리 숫자에 대해서 안정적인 정렬 알고리즘을 적용하면 정렬이 완료됩니다.

MSD 기수 정렬

MSD 기수 정렬 방식으로 아래의 배열을 정렬해 봅시다.

arr = [288, 265, 482, 095, 361, 068, 185, 100]

LSD 기수 정렬 이 일-십-백 의 자리 순서대로 정렬을 수행했다면, MSD 기수 정렬 은 가장 높은 자리수를 기준으로 데이터를 정렬한 후 높은 자리에서 정렬된 부분집합에 대해 재귀적으로 다음 높은 자리수를 기준으로 정렬하는 방식입니다.

arr = [288, 265, 482, 095, 361, 068, 185, 100]

# 백의 자리 숫자로 정렬..
# 백의 자리 숫자 기준 2, 2, 4, 0, 3, 0, 1, 1]
arr = [095, 068, 185, 100, 288, 265, 361, 482]

# (095, 068), (185, 100), (288, 265), (361), (482)

위처럼 백의 자리 숫자를 기준으로 배열을 정렬하면, 백의 자리 숫자들에 대해 (095, 068), (185, 100), (288, 265), (361), (482) 와 같은 부분집합이 생기게 됩니다. 이제 이 부분집합들에 대해서 다음 자릿수에 대한 정렬을 수행하면 됩니다.

arr = [288, 265, 482, 095, 361, 068, 185, 100]

# 백의 자리 숫자로 정렬..
# 백의 자리 숫자 기준 2, 2, 4, 0, 3, 0, 1, 1]
arr = [095, 068, 185, 100, 288, 265, 361, 482]

# 십의 자리 숫자로 정렬..
# 십의 자리 숫자 기준 (9, 6), (8, 0), (8, 6), (6), (8)
arr = [068, 095, 100, 185, 265, 288, 361, 482]

# 일의 자리 숫자로 정렬..
arr = [068, 095, 100, 185, 265, 288, 361, 482]

기수 정렬의 성능 분석과 특징

• 기수 정렬의 시간 복잡도는 O(n) 입니다.
  • 자릿수가 d, 숫자의 개수가 n 이고 각 숫자에 대해서 선형 시간에 동작하는 계수 정렬을 사용한다고 가정한다면, 각 자리에 대해서 정렬하는 데에는 O(n) 의 시간이 걸립니다.
  • 그리고 각 자릿수에 대해서 반복해야 하므로 O(dn) 의 시간이 걸리는데, d 를 상수로 취급할 수 있다면 기수 정렬은 O(n) 의 시간 복잡도를 보입니다.
• 기수 정렬은 자릿수별로 선형 시간에 동작하는 계수 정렬을 적용하기 때문에, 전체 정렬은 자릿수에 비례하여 동작합니다. 자릿수 d, 즉 계수 정렬에서의 입력값이 n 과 무관하다면 d 는 상수로 볼 수 있는데, 이 때 기수 정렬은 선형 시간에 동작합니다.
• 기수 정렬은 안정적인 정렬 알고리즘입니다. 같은 데이터가 있을 때, 정렬 후에도 그들의 상대적인 위치가 유지됩니다.
• 기수 정렬은 제자리 정렬 알고리즘이 아닙니다. 자릿수별로 정렬할 때 각 자릿수에 대해 제자리 정렬이 아닌 계수 정렬을 적용하므로, 전체 데이터 개수와 자릿수 크기만큼의 추가로 요구되게 됩니다.