[swift] Swift에서 쉘 정렬 알고리즘을 구현하는 방법
쉘 정렬(shell sort) 알고리즘은 삽입 정렬(insertion sort)을 기반으로 한 정렬 알고리즘입니다. 데이터를 간격(h-gap)만큼 떨어져 있는 그룹으로 나눈 후, 각 그룹을 삽입 정렬을 사용하여 정렬하고, 간격을 점점 줄여나가며 정렬을 반복하는 방식입니다. 이 알고리즘은 장점인 평균 시간복잡도가 O(n log n)으로 상당히 빠른 속도를 가지고 있습니다.
쉘 정렬 알고리즘 구현 예시
func shellSort<T: Comparable>(_ array: inout [T]) {
var gap = array.count / 2
while gap > 0 {
for i in gap..<array.count {
let temp = array[i]
var j = i
while j >= gap && array[j - gap] > temp {
array[j] = array[j - gap]
j -= gap
}
array[j] = temp
}
gap /= 2
}
}
var numbers = [9, 5, 2, 8, 1, 10, 4, 7, 3, 6]
shellSort(&numbers)
print(numbers) // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
위의 예시는 Swift로 쉘 정렬 알고리즘을 구현한 코드입니다. 주어진 배열을 간격을 설정하여 그룹으로 나눈 후, 각 그룹을 삽입 정렬을 사용하여 정렬합니다. 간격을 점점 줄여나가면서 정렬을 반복합니다.
위의 코드 예시에서는 shellSort 함수를 정의하고, 제네릭 함수로 구현하여 정수 배열 뿐만 아니라 다른 타입의 배열에서도 사용할 수 있도록 하였습니다. 입력으로 주어진 배열을 inout 매개변수로 받아서 원본 배열을 직접 수정합니다.
위의 코드를 실행하면 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]과 같이 정렬된 결과가 출력됩니다.
결론
Swift에서 쉘 정렬 알고리즘을 구현하는 방법을 살펴보았습니다. 쉘 정렬은 평균 시간복잡도가 O(n log n)으로 빠른 정렬 알고리즘 중 하나입니다. 위의 예시 코드를 활용하여 다양한 데이터를 효율적으로 정렬할 수 있습니다.