Colin's Blog
[swift] Swift에서 병합 정렬 알고리즘을 구현하는 방법

병합 정렬(Merge Sort)은 배열을 반으로 나눈 후 재귀적으로 각 부분을 정렬하고, 정렬된 두 부분을 합치는 과정으로 정렬을 수행하는 알고리즘입니다. 이번 글에서는 Swift 언어를 사용하여 병합 정렬 알고리즘을 구현하는 방법에 대해 알아보겠습니다.

알고리즘 개요

  1. 배열을 반으로 나눈다.
  2. 재귀적으로 각 부분을 정렬한다.
  3. 분할된 부분을 병합한다.

Swift 코드 예시

func mergeSort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else {
        return array
    }
    
    let middle = array.count / 2
    let leftArray = Array(array[..<middle])
    let rightArray = Array(array[middle...])
    
    return merge(mergeSort(leftArray), mergeSort(rightArray))
}

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var result: [Int] = []
    var leftIndex = 0
    var rightIndex = 0
    
    while leftIndex < left.count && rightIndex < right.count {
        if left[leftIndex] < right[rightIndex] {
            result.append(left[leftIndex])
            leftIndex += 1
        } else {
            result.append(right[rightIndex])
            rightIndex += 1
        }
    }
    
    if leftIndex < left.count {
        result.append(contentsOf: left[leftIndex...])
    }
    
    if rightIndex < right.count {
        result.append(contentsOf: right[rightIndex...])
    }
    
    return result
}

코드 설명

  1. mergeSort 함수는 입력된 배열을 반으로 나눈 후 재귀적으로 각 부분을 정렬합니다. 배열의 크기가 1보다 작거나 같으면 정렬할 필요가 없기 때문에 기저 조건으로 설정합니다.
  2. merge 함수는 두 개의 정렬된 배열을 입력으로 받아, 두 배열을 병합하여 정렬된 결과를 반환합니다. 두 개의 포인터(leftIndex, rightIndex)를 사용하여 각 배열의 요소를 비교하고 병합할 배열(result)에 삽입합니다.
  3. 분할과 병합이 모두 완료되면 최종적으로 정렬된 배열을 반환합니다.

사용 예시

let array = [4, 2, 9, 6, 1, 5, 3, 8, 7]
let sortedArray = mergeSort(array)

print(sortedArray) // [1, 2, 3, 4, 5, 6, 7, 8, 9]

위의 예시 코드에서는 주어진 배열을 병합 정렬 알고리즘을 사용하여 정렬한 후 결과를 출력합니다.

마무리

Swift 언어를 사용하여 병합 정렬 알고리즘을 구현하는 방법에 대해 알아보았습니다. 이 알고리즘은 배열을 효율적으로 정렬하는데 사용되며, 핵심적인 분할과 병합 과정을 재귀적으로 구현하는 것이 주요 포인트입니다. 알고리즘의 이해와 함께 실제 코드 구현을 통해 병합 정렬에 대해 더욱 깊이 알아가길 바랍니다.

© 2018 Colin. All rights reserved.