[Algorithm] 정렬: 버킷 정렬, 기수 정렬

+ 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다.

비교에 기반한 정렬의 시간 복잡도 한계

=> 두 원소의 비교에 기반한 정렬 알고리즘은 Θ(nlogn)보다 빠르게 동작할 수 없다.

---

버킷 정렬 (Bucket sort)

정렬될 데이터가 자릿수라는 개념이 있다면 이를 이용한다.

 

ex) 정렬될 데이터가 택배 주소라면, 전체를 다 보지 않고 처음 위치를 보고 데이터를 분류할 수 있다.

 

분류한 데이터를 각각 정렬하고, 이를 이으면 정렬이 완성된다.

 

< 가장 좋은 경우 >

- c개의 버킷으로 모든 원소가 균등하게 배분되어 각각 n / c개가 들어갔을 경우

=> n / c개를 Θ((n/c) log (n/c)) 시간에 정렬할 수 있고, 이를 다시 합치면

=> c(n/c) log(n/c) = n(logn - log c)

 

< 가장 나쁜 경우 >

- 하나의 버킷으로 모든 원소가 몰렸을 경우

=> 버킷을 사용하지 않은 것과 같다.

---

Stable Sort

- 둘 이상의 키로 이루어진 데이터를 정렬할 때 발생하는 문제

 

(a, b), (a, c), (a, d), (a, d), ...

1. 첫 번째 원소가 작은 쪽이 앞에 온다.

2. 첫 번째 원소의 크기가 같다면 두 번째 원소를 비교하여 작은 것이 앞에 온다.

 

+ 동점일 때는 원래 이전의 순서가 유지된다.

 

=> 두 번째 원소들을 먼저 정렬하고, 첫 번째 원소들을 정렬해야한다! (생각과 반대)

Why? 최종 정렬 결과는 마지막에 정렬한 결과이다.

 

=> 같은 원소들이 있을 때 정렬된 다음의 순서가 정렬하기 전의 순서와 일치하면 Stable Sort이다.

 

즉, 동일한 값을 갖고 있는 원소들의 상대적인 순서가 정렬 전과 정렬 후에도 유지되는 정렬 방법이다.

---

Stable Sort 예제

2차원 좌표계의 점들을 다음 기준에 따라 정렬하라.

 

1. x 좌표에 따라 오름차순으로 정렬한다.

2. x 좌표가 같다면 y 좌표에 따라 오름차순으로 정렬한다.

 

=> y 좌표를 먼저 정렬하고, x 좌표를 정렬해야한다!

 

초기: (1, 5), (2, 4), (2, 2), (3, 1)

 

y 좌표 정렬: (3, 1), (2, 2), (2, 4), (1, 5)

 

x 좌표 정렬: (1, 5), (2, 2), (2, 4), (3, 1)

 

< 주의 >

x좌표를 정렬할 때 동점인 경우 정렬하는 과정에서 순서가 바뀌면 안된다.

ex) (2, 2), (2, 4)의 순서는 x 좌표가 2로 동일하므로, 순서가 바뀌지 않는다.

---

정렬 방법과 Stable Sort 여부

동점인 두 원소의 자리를 바꾸지 않도록 했을 때, 정렬이 가능하다면 Stable Sort이다.

 

< 퀵 정렬 >

=> 정렬 기준이 맨 처음 원소라면 Stable Sort이다.

그렇지 않다면 정렬 기준과 원래 원소의 위치를 고려해야한다.

(기준 원소와 비교 원소가 동점일 때, 원래 위치가 앞 인지, 뒤 인지 고려) 

 

< 버블 정렬 >

=> Stable Sort

 

< 삽입 정렬 >

=> Stable Sort

 

< 병합 정렬 >

=> Stable Sort

병합 시 동점인 두 원소가 존재하면 왼쪽에 있는 원소를 먼저 떼서 붙인다.

 

< 힙 정렬 >

=> Stable Sort가 아니다.

순서 정보가 힙에 들어가는 과정에서 파괴된다. (원래의 위치가 파괴된다.)

---

기수 정렬 (radix sort)

완전히 비교를 제외한 정렬 방법이다. (버킷 정렬과 Stable의 응용)

 

낮은 자리에서 높은 자리로 기준을 바꾸어 가면서 정렬한다.

- 실제로 정렬을 한다기 보다, 0 ~ 9까지 버킷이 있고 이 버킷에 숫자를 넣어간다고 생각하면 된다.

- 리스트를 차례로 읽어나가면서 순서를 지킨다. (Stable Sort)

 

기존: 153, 262, 037, 598, 433, 855

 

1의 자리 버킷 정렬: 262, 153, 433, 855, 037, 598 

 

10의 자리 버킷 정렬: 433, 037, 153, 855, 262, 598

 

100의 자리 버킷 정렬: 037, 153, 262, 433, 598, 855

 

=> 자릿수를 보고 해당 자리 버킷의 위치에 넣는다.

 

기수 정렬 예 (화살표는 Stable Sort)

 

< 시간 복잡도 >

=> Θ(r×n)

r: 숫자의 자릿수

n: n은 정렬된 수

 

import math

def radixsort(arr):
    # 입력 배열(arr)에서 가장 큰 수를 찾습니다.
    max_num = max(arr)
    
    # 가장 큰 수의 자릿수를 계산합니다.
    max_digits = int(math.log10(max_num)) + 1
    
    for digit_place in range(max_digits):
        # 각 자릿수를 기준으로 버킷을 초기화
        bucket = [[] for _ in range(10)]
        
        # 배열을 순회하면서 해당 자릿수의 값을 버킷에 배치
        for num in arr:
            digit = (num // 10**digit_place) % 10
            bucket[digit].append(num)
        
        # 버킷에 저장된 요소들을 다시 배열에 병합
        arr = []
        for i in range(10):
            arr.extend(bucket[i]) # arr리스트 뒤에 bucket 추가
    
    return arr

x = [153, 262, 37, 598, 433, 855]
result = radixsort(x)
print(result)