[Algorithm]파이썬으로 배우는 기수 정렬: 알고리즘 마스터하기

이번 포스팅에서는 기수 정렬에 대해 자세히 알아보겠습니다. 기수 정렬은 숫자나 문자열을 효율적으로 정렬할 수 있는 강력한 알고리즘 중 하나입니다. 이 글에서는 기수 정렬의 기본 개념부터 파이썬으로 구현하는 방법까지 단계별로 설명하겠습니다. 기수 정렬의 장단점과 성능 분석, 그리고 예제 코드를 통해 여러분이 쉽게 이해할 수 있도록 도와드릴 것입니다.

≣ 목차

• 기수 정렬이란 무엇인가?📘
• 기수 정렬의 원리🔍
• 기수 정렬의 장점과 단점⚖️
• 파이썬으로 구현하기🐍
• 성능 분석 및 비교📊

---

01. 기수 정렬이란 무엇인가?📘

기수 정렬(Radix Sort)은 정렬 알고리즘 중 하나로, 데이터를 자릿수 별로 비교하여 정렬하는 방식입니다. 기수 정렬은 특히 숫자나 문자열의 정렬에 효과적이며, 안정 정렬 알고리즘으로 분류됩니다. 이는 같은 값이 여러 개 있을 때 그 값들의 상대적인 순서가 변하지 않는다는 것을 의미합니다.

---

02. 기수 정렬의 원리🔍

기수 정렬은 자리수를 기준으로 여러 개의 버킷을 사용하여 데이터를 정렬합니다. 각 자릿수에 해당하는 데이터를 적절한 버킷에 배분하고, 이 버킷들은 큐 구조를 사용하여 데이터를 저장합니다. 이후 버킷의 데이터를 순서대로 다시 모아 정렬을 완료합니다.

단계별 과정

1. 최소 자리수부터 정렬: 먼저 가장 작은 자릿수(1의 자리)부터 시작하여 데이터를 정렬합니다.
2. 다음 자리수로 이동: 그 다음 자릿수(10의 자리)로 이동하여 다시 정렬합니다.
3. 최대 자리수까지 반복: 최대 자리수까지 이 과정을 반복합니다.

각 단계에서 데이터는 0부터 9까지의 버킷(큐)으로 배분됩니다. 예를 들어, 1의 자리를 기준으로 데이터가 정렬되면, 다음으로 10의 자리를 기준으로 버킷에 다시 배분합니다.

큐 자료 구조에 대한 내용은 아래 포스팅을 참고해 주세요😁

[자료구조]파이썬 큐 자료구조 완벽 가이드: 기본 개념부터 실전 활용까지

 

---

03. 기수 정렬의 장점과 단점⚖️

기수 정렬은 다음과 같은 장점과 단점을 가지고 있습니다.

장점

1. 빠른 속도: 기수 정렬은 선형 시간 복잡도(O(nk))를 가지므로, 데이터의 크기와 상관없이 일정한 속도로 정렬할 수 있습니다.
2. 안정 정렬: 동일한 값의 순서가 유지되므로 안정 정렬로 사용할 수 있습니다.

단점

1. 공간 복잡도: 많은 메모리를 사용하기 때문에 큰 데이터 집합에서는 비효율적일 수 있습니다.
2. 자료형 제한: 숫자나 문자열 등 특정 자료형에만 적용할 수 있습니다. (한글, 한자, 실수 자료형은 불가)

---

04. 파이썬으로 구현하기🐍

from collections import deque  # deque를 사용하여 큐를 구현

def radix_sort(arr):
    # 가장 큰 숫자를 찾아 최대 자릿수를 계산
    max1 = max(arr)
    exp = 1  # 자리수를 의미하는 변수, 초기값은 1 (1의 자리)

    # 최대 자릿수만큼 정렬 반복
    while max1 // exp > 0:
        # 0-9까지의 큐 리스트 생성
        buckets = [deque() for _ in range(10)]
        
        # 현재 자릿수에 따라 버킷에 데이터 배분
        for num in arr:
            index = (num // exp) % 10  # 현재 자릿수에 해당하는 숫자 추출
            buckets[index].append(num)  # 해당 숫자에 맞는 버킷에 데이터 추가
        
        # 버킷에 담긴 데이터를 차례대로 배열에 다시 저장
        i = 0
        for bucket in buckets:
            while bucket:
                arr[i] = bucket.popleft()  # 버킷에서 데이터를 꺼내 배열에 저장
                i += 1
        
        exp *= 10  # 다음 자리수로 이동 (1 -> 10 -> 100 ...)
        
# 예제 사용
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("정렬된 배열:", arr)

1. 모듈 임포트

from collections import deque

• deque 모듈을 사용하여 큐를 구현합니다. 큐는 FIFO(First In First Out) 구조로, 기수 정렬에서 각 자릿수별로 데이터를 버킷에 저장하는 데 유용합니다.

2. radix_sort 함수

def radix_sort(arr):

• radix_sort 함수는 배열 arr을 입력받아 기수 정렬을 수행합니다.

3. 최대 자릿수 계산

max1 = max(arr)
exp = 1  # 자리수를 의미하는 변수, 초기값은 1 (1의 자리)

• 배열에서 가장 큰 숫자를 찾아 그 숫자의 최대 자릿수를 계산합니다. exp는 현재 정렬할 자릿수를 의미하며, 초기값은 1로 설정하여 1의 자리부터 시작합니다.

4. 자릿수별 정렬 반복

while max1 // exp > 0:
    buckets = [deque() for _ in range(10)]

• 최대 자릿수까지 반복합니다. 각 반복마다 0부터 9까지의 버킷(큐) 리스트를 생성합니다.

5. 버킷에 데이터 배분

for num in arr:
    index = (num // exp) % 10
    buckets[index].append(num)

• 현재 자릿수에 따라 각 숫자를 적절한 버킷에 배분합니다. 예를 들어, num이 170이고 exp가 1일 때, index는 0이 되어 0번째 버킷에 170을 추가합니다.

6. 배열에 데이터 재저장

i = 0
for bucket in buckets:
    while bucket:
        arr[i] = bucket.popleft()
        i += 1

• 버킷에 있는 데이터를 꺼내 원래 배열에 다시 저장합니다. 각 버킷에서 데이터를 popleft하여 배열에 순서대로 넣습니다.

7. 다음 자리수로 이동

exp *= 10

• exp를 10배로 증가시켜 다음 자릿수로 이동합니다. (1의 자리 -> 10의 자리 -> 100의 자리...)

8. 예제 사용

arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("정렬된 배열:", arr)

• radix_sort 함수를 호출하여 배열을 정렬하고 결과를 출력합니다.

---

05. 성능 분석 및 비교📊

시간 복잡도

• 최악의 경우 시간 복잡도: O(d * (n + k))
  - d: 자릿수의 최대 개수
  - n: 정렬할 요소의 개수
  - k: 자릿수 값의 범위 (예: 10진수의 경우 k=10)
• 평균 시간 복잡도: O(d * n)
• 최선의 경우 시간 복잡도: O(d * n)

공간 복잡도

• 기수 정렬은 추가적인 메모리를 필요로 합니다. 주로 각 자릿수별로 데이터를 임시로 저장할 배열을 사용하므로, O(n + k)의 공간을 사용합니다.
• 또한, 입력 데이터를 수정하지 않으므로 추가적인 메모리 사용이 발생할 수 있습니다.

안정성

• 기수 정렬은 안정적인 정렬 알고리즘입니다. 즉, 같은 키를 가진 요소들이 원래의 순서를 유지합니다. 이 특성은 특정 경우에 유용할 수 있습니다.

적합성

• 기수 정렬은 주로 정수나 고정 길이의 문자열 정렬에 적합합니다.
• 자릿수의 범위가 작고 자릿수가 상대적으로 적은 경우에 특히 효과적입니다.