[Algorithm] 기수 정렬(Radix Sort) 알고리즘(Swift 구현)

[Algorithm] 기수 정렬(Radix Sort) 알고리즘(Swift 구현)

 

 

1. 기수 정렬이란?

 

기수 정렬은 계수 정렬과 비슷한 면이 있다. 계수 정렬은 인덱스를 활용해서 새로운 배열을 만들어 차례로 정렬을 시켜주는 알고리즘인데, 기수정렬은 이와 비슷하게 비교연산을 수행하지 않고 데이터의 각 자릿수를 낮은 자리수부터 가장 큰 자리수까지 올라가면서 정렬을 수행해준다. 그렇기 때문에 문자열에도 적용이 가능한 정렬방법이다. 하지만 '자릿수'가 존재하지 않는다면 데이터를 기수정렬로 정렬하는 것이 불가능하다.

 

 

2. 기수 정렬

 

var array = [51, 3(1), 29, 3(2), 33, 105] 가 있다고 가정해보자!

(3이 2개가 있는데 이는 안정 정렬인지를 보기 위함이다. 그냥 둘 다 정수 3으로 생각하면 된다.)

 

1) 기수정렬의 과정

 

(1) 첫 번째 자리(숫자에서는 1의 자리)부터 순서대로 bucket에 담는다.

 

bucket은 0부터 9까지 총 10개의 공간이 있다고 생각하면 된다. 거기에 현재 1의 자리를 보고 bucket의 자리에 원소를 넣는다고 생각해보자.

이런 식으로 첫 번째 자리의 숫자가 bucket으로 비교가 되어서 새롭게 정렬이 된다.

 

 

(2) 두 번째 자리(숫자에서는 10의 자리)를 기준으로 순서대로 bucket에 담는다.

한 자리 수인 3의 경우 10의 자리수는 당연히 0이다. 그래서 0쪽의 bucket에 가서 담긴 것이고, 105는 순서상 마지막에 담길 수 밖에 없었다.

 

(3) 세 번째 자리(숫자에서는 100의 자리)를 기준으로 순서대로 bucket에 담는다.

 

(4) 버킷 0 부분에 모든 원소들이 모일 때까지 반복한다. 이렇게 되면, 오름차순으로 정렬된 배열을 볼 수 있을 것이다.

 

 

2) 시간복잡도와 공간복잡도

 

시간복잡도는 O(d * (n + b)) 이다. 여기서 d는 정렬할 숫자의 자릿수, b는 10이다.

공간복잡도는 중간에 bucket 만큼의 공간이 더 필요하다. 영문의 경우 알파벳 숫자만큼의 bucket이 필요하며 그 안에 데이터가 N만큼 들어가기 때문에 O(2N) 정도라고 할 수 있겠다.

 

또한 위에서 보았듯 3(1), 3(2)가 그대로 순서를 유지하면서 정렬된 것을 볼 수 있다. 기수정렬의 방법의 특성 때문에 몇 번의 정렬을 더 한다 하더라도 3(1)과 3(2)는 계속 같을 것이다. 따라서 '안정 정렬'이다.

 

 

3. Swift로 구현한 코드

 

func radixSort(_ array: inout [Int]) -> [Int] {
    let radix = 10  // 0 ~ 9 까지의 10개의 자릿수
    var done = true
    var index: Int
    var digit = 1
    
    while done {
        var buckets: [[Int]] = [] // 10개의 버킷을 2중 배열로 선언
        for _ in 1 ... radix {
            buckets.append([])
        }

        for number in array {
            index = number / digit // 해당 요소의 자릿수의 숫자를 추출
            buckets[index % radix].append(number) // 해당 자릿수 버킷에 데이터 추가
            if done && index > 0 {
                done = false
            }
        }

        var i = 0

        for j in 0 ..< radix {
            let bucket = buckets[j]
            for number in bucket {
                array[i] = number
                i += 1
            }
        }

        digit *= radix  // 다음 자릿수 비교
    }
    
    return array
}

 

4. 정리

 

비교적 쉬운 기수정렬을 알아보았다. Tim Sort를 마지막으로 정렬을 마무리하고 다른 알고리즘으로 넘어갈 생각이다....