도수 정렬은 일련의 숫자들을 정렬하는 효율적인 알고리즘입니다. 이 알고리즘은 각 숫자의 등장 횟수를 세는 도수표를 사용하여 정렬을 수행합니다. Swift에서 도수 정렬 알고리즘을 구현하는 방법을 알아보겠습니다.
Step 1: 도수표 작성
먼저, 주어진 숫자 배열에서 각 숫자의 등장 횟수를 세는 도수표를 작성해야 합니다. 이를 위해 Dictionary를 사용할 수 있습니다.
func createFrequencyTable(array: [Int]) -> [Int: Int] {
var frequencyTable = [Int: Int]()
for number in array {
frequencyTable[number, default: 0] += 1
}
return frequencyTable
}
위의 코드는 주어진 숫자 배열에서 각 숫자의 등장 횟수를 세는 도수표를 작성하는 함수입니다. frequencyTable이라는 빈 딕셔너리를 선언한 후, 배열을 순회하면서 각 숫자의 등장 횟수를 세고, 딕셔너리에 해당 숫자를 키로 등장 횟수를 값으로 저장합니다.
Step 2: 누적 도수표 작성
다음으로, 도수표에서 누적 도수표를 작성해야 합니다. 누적 도수표는 각 숫자 이전까지 등장한 총 횟수를 나타냅니다.
func createCumulativeFrequencyTable(frequencyTable: [Int: Int]) -> [Int: Int] {
var cumulativeFrequencyTable = [Int: Int]()
var cumulativeSum = 0
for (number, frequency) in frequencyTable.sorted(by: { $0.0 < $1.0 }) {
cumulativeSum += frequency
cumulativeFrequencyTable[number] = cumulativeSum
}
return cumulativeFrequencyTable
}
위의 코드는 주어진 도수표에서 누적 도수표를 작성하기 위한 함수입니다. cumulativeFrequencyTable이라는 빈 딕셔너리와 cumulativeSum이라는 변수를 선언한 후, 도수표를 순차적으로 탐색하며 누적 도수값을 계산하여 딕셔너리에 저장합니다.
Step 3: 정렬된 배열 생성
마지막으로, 누적 도수표를 사용하여 정렬된 배열을 생성해야 합니다.
func sortArrayUsingFrequency(array: [Int], cumulativeFrequencyTable: [Int: Int]) -> [Int] {
var sortedArray = [Int](repeating: -1, count: array.count)
for number in array {
let index = cumulativeFrequencyTable[number, default: 0]
sortedArray[index - 1] = number
cumulativeFrequencyTable[number] = index - 1
}
return sortedArray
}
위의 코드는 주어진 배열을 도수 정렬 알고리즘을 사용하여 정렬하는 함수입니다. sortedArray라는 초기화된 배열을 선언한 후, 주어진 배열을 순회하면서 해당 숫자의 누적 도수값을 인덱스로 사용하여 sortedArray에 해당 숫자를 저장합니다. 또한, 누적 도수표를 업데이트하여 정렬의 정확성을 유지합니다.
사용 예시
let numbers = [5, 3, 8, 2, 5, 1, 6, 3, 8, 2]
let frequencyTable = createFrequencyTable(array: numbers)
let cumulativeFrequencyTable = createCumulativeFrequencyTable(frequencyTable: frequencyTable)
let sortedArray = sortArrayUsingFrequency(array: numbers, cumulativeFrequencyTable: cumulativeFrequencyTable)
print(sortedArray) // [1, 2, 2, 3, 3, 5, 5, 6, 8, 8]
위의 예시는 주어진 숫자 배열을 도수 정렬 알고리즘을 사용하여 정렬하는 방법을 보여줍니다. 주어진 숫자 배열 [5, 3, 8, 2, 5, 1, 6, 3, 8, 2]를 정렬하면 [1, 2, 2, 3, 3, 5, 5, 6, 8, 8]이 출력됩니다.
이제 Swift에서 도수 정렬 알고리즘을 구현하는 방법에 대해 알게 되었습니다. 도수 정렬은 효율적인 알고리즘으로, 정렬해야 하는 숫자의 범위가 작을 때 유용하게 사용될 수 있습니다.