[swift] 정렬 함수를 사용하여 기수 정렬하기

05 Dec 2023

swift

기수 정렬은 정렬 알고리즘 중 하나로, 비교 연산 없이 정렬하는 알고리즘입니다. 이 알고리즘은 숫자의 자릿수를 비교하여 정렬하는 특징을 가지고 있습니다.

Swift에서는 Array 타입에 기본적으로 정렬 함수인 sorted()와 sort()를 제공합니다. 이 함수를 사용하여 기수 정렬을 구현해보겠습니다.

기수 정렬 알고리즘 구현하기

func radixSort(_ array: inout [Int]) {
    // 배열의 최대값 구하기
    guard let max = array.max() else {
        return
    }

    // 최대값의 자릿수 구하기
    var divisor = 1
    while max / divisor > 0 {
        // 버킷 배열 생성
        var buckets: [[Int]] = Array(repeating: [], count: 10)

        // 배열을 버킷에 분배
        for element in array {
            let digit = (element / divisor) % 10
            buckets[digit].append(element)
        }

        // 버킷의 순서대로 배열 재구성
        array = buckets.flatMap { $0 }

        // 자릿수 증가
        divisor *= 10
    }
}

기수 정렬 실행하기

var array = [170, 45, 75, 90, 802, 24, 2, 66]
radixSort(&array)
print(array) // [2, 24, 45, 66, 75, 90, 170, 802]

위의 코드는 주어진 배열을 기수 정렬하는 함수와 실행문입니다. 정렬 결과는 [2, 24, 45, 66, 75, 90, 170, 802]와 같이 나옵니다.

기수 정렬은 비교 연산 없이 자릿수를 이용하여 정렬하는 특징을 가지고 있어 빠른 속도로 정렬할 수 있습니다. 하지만 정렬할 데이터가 많을 경우 메모리 사용량이 크게 증가할 수 있으니 주의해야 합니다.

자세한 내용은 기수 정렬(Wikipedia)을 참고하세요.