[swift] Swift에서 힙 정렬 알고리즘을 구현하는 방법

05 Dec 2023

swift

힙 정렬은 효율적인 정렬 알고리즘 중 하나로, 특히 대량의 데이터를 정렬할 때 사용됩니다. 이번 글에서는 Swift를 사용하여 힙 정렬 알고리즘을 구현하는 방법을 살펴보겠습니다.

1. 힙 정렬 알고리즘 이해하기

힙 정렬은 힙 자료구조를 이용하여 정렬하는 알고리즘입니다. 힙은 완전 이진 트리로 구성되어 있으며, 부모 노드의 값이 자식 노드의 값보다 큰(max-heap) 또는 작은(min-heap) 이진 트리입니다.

힙 정렬 알고리즘은 다음과 같은 단계로 이루어집니다:

주어진 데이터를 힙으로 구성합니다.
최대 힙에서 최댓값(또는 최소 힙에서 최솟값)을 가져옵니다.
힙에서 가져온 값을 배열의 마지막 요소와 교환합니다.
배열의 마지막 요소를 제외하고 다시 힙을 조정합니다(재배열).
2-4단계를 반복하여 정렬이 완료될 때까지 진행합니다.

2. Swift로 힙 정렬 구현하기

아래는 Swift로 힙 정렬을 구현한 예시 코드입니다:

func heapify<T>(_ array: inout [T], _ n: Int, _ i: Int) where T: Comparable {
    var largest = i
    let left = 2 * i + 1
    let right = 2 * i + 2

    if left < n && array[left] > array[largest] {
        largest = left
    }

    if right < n && array[right] > array[largest] {
        largest = right
    }

    if largest != i {
        array.swapAt(i, largest)
        heapify(&array, n, largest)
    }
}

func heapSort<T>(_ array: inout [T]) where T: Comparable {
    let n = array.count

    for i in (0...(n/2 - 1)).reversed() {
        heapify(&array, n, i)
    }

    for i in (0...(n-1)).reversed() {
        array.swapAt(0, i)
        heapify(&array, i, 0)
    }
}

var numbers = [9, 4, 7, 1, 6, 3, 8, 2, 5]
heapSort(&numbers)
print(numbers) // [1, 2, 3, 4, 5, 6, 7, 8, 9]

위의 코드에서 heapify 함수는 힙을 구성하고 조정하는 역할을 합니다. heapSort 함수는 주어진 배열을 힙으로 구성한 후, 정렬을 진행합니다. 마지막으로, 정렬된 배열이 출력됩니다.

3. 정리

Swift를 사용하여 힙 정렬 알고리즘을 구현하는 방법을 알아보았습니다. 힙 정렬은 대량의 데이터를 효율적으로 정렬할 수 있는 알고리즘이므로, 대용량 데이터를 다루는 경우에 유용하게 활용될 수 있습니다.

더 자세한 내용은 Swift 공식 문서를 참고하시기 바랍니다.