四十三庵

蔀の雑記帳

Merge Sort(マージソート)

データ構造とアルゴリズム (新・情報 通信システム工学)

  • 最悪計算量でもO(NlogN)
  • メモリ領域はO(N)分食う
  • フォンノイマンが考えたアルゴリズムらしいが、考え方はシンプルだし、計算効率いいし実用的
  • 配列の真ん中から要素を分けて、それを繰り替えして、要素二つにしたらmerge()
    mergeされた配列は再帰的にどんどんmergeされる

実装

import Foundation

var order = 0

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

func merge(leftArray: [Int], rightArray: [Int]) -> [Int] {
    var leftIndex = 0
    var rightIndex = 0
    var mergedArray = [Int]()
    while leftIndex < leftArray.count && rightIndex < rightArray.count {  //最初ここをなぜか==にしていてエラーになっていた
        let leftElement = leftArray[leftIndex]
        let rightElement = rightArray[rightIndex]
        if leftElement < rightElement {
          mergedArray.append(leftElement)
          leftIndex += 1
        } else if leftElement > rightElement {
          mergedArray.append(rightElement)
          rightIndex += 1
        } else {
          mergedArray.append(leftElement)
          leftIndex += 1
          mergedArray.append(rightElement)
          rightIndex += 1
        }
        order += 1
    }
    while leftIndex < leftArray.count {
        mergedArray.append(leftArray[leftIndex])
        leftIndex += 1
        order += 1
    }
    while rightIndex < rightArray.count {
        mergedArray.append(rightArray[rightIndex])
        rightIndex += 1
        order += 1
    }
    return mergedArray
}

order = 0
var array = [2, 1]
mergeSort(array: array)
print("計算量はO(", order, ")")

order = 0
array = [1, 2, 4, 3, 6, 5]
mergeSort(array: array)
print("計算量はO(", order, ")")

order = 0
array = (1...20).map { $0 }
mergeSort(array: array)
print("計算量はO(", order, ")")

order = 0
array = (1...1000).map { $0 }
mergeSort(array: array)
print("計算量はO(", order, ")")

//計算量はO( 2 )
//計算量はO( 16 )
//計算量はO( 88 )
//計算量はO( 9976 )