소개

카운팅 정렬(Counting Sort)은 입력 배열의 각 원소의 값을 카운트하여 정렬하는 알고리즘입니다. 비교 연산 없이 정렬을 수행하기 때문에 다른 정렬 알고리즘에 비해 빠른 속도를 가지고 있습니다.

이 글에서는 Swift의 정렬 함수를 사용하여 카운팅 정렬을 구현하는 방법에 대해 알아보겠습니다.

코드

func countingSort(_ array: [Int]) -> [Int] {
    guard let max = array.max() else {
        return array
    }
    
    var countingArray = Array(repeating: 0, count: max + 1)
    var sortedArray = Array(repeating: 0, count: array.count)
    
    for num in array {
        countingArray[num] += 1
    }
    
    var currentIndex = 0
    for (num, count) in countingArray.enumerated() {
        for _ in 0..<count {
            sortedArray[currentIndex] = num
            currentIndex += 1
        }
    }
    
    return sortedArray
}

let array = [4, 2, 8, 3, 5, 3, 2]
let sortedArray = countingSort(array)
print(sortedArray)  // [2, 2, 3, 3, 4, 5, 8]

설명

1. 우선 입력 배열에서 최대 값을 찾아야 합니다. 입력 배열이 비어있는 경우에는 입력 배열 그대로를 반환합니다.
2. 입력 배열의 최대 값 + 1 크기의 카운팅 배열과 정렬된 배열을 선언합니다.
3. 입력 배열을 순회하며 각 원소의 값을 카운팅 배열에 추가합니다.
4. 카운팅 배열을 순회하면서 각 원소를 정렬된 배열에 추가합니다. 이때, 카운팅 배열의 값이 0이 아닌 경우에만 추가합니다.
5. 정렬된 배열을 반환합니다.

시간 복잡도

카운팅 정렬의 시간 복잡도는 O(n+k)입니다. n은 입력 배열의 크기이고, k는 입력 배열의 최대 값입니다. 따라서 최악의 경우에도 선형 시간에 정렬을 수행할 수 있습니다.

결론

이번 글에서는 Swift의 정렬 함수를 사용하여 카운팅 정렬을 구현하는 방법에 대해 알아보았습니다. 카운팅 정렬은 입력 배열의 크기와 최대 값을 알고 있는 경우에 유용한 정렬 알고리즘입니다.

더 많은 정보를 원하시면 아래의 참고 자료를 참고해주세요.

참고 자료

• Counting Sort (Wikipedia)