四十三庵

蔀の雑記帳

Quick Sort(クイックソート)

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

  • 配列の最初の要素と二番目の要素の大きい方をpivotとして、その値との大小関係を使ってSortする
  • 計算量は平均でO(NlogN)
  • 最悪の場合はO(N2)
  • 本の通り実装しようとしたら、Arrayはstructなので再帰ができなくて、 しかも引数のArrayはimmutabelで直接操作できないので、返り値に変更後の配列を持たせようとしたが、
    書いている途中でよくわからなくなった。Binray Search Treeのときもこんな感じだったな

実装

※途中でグダグダになったもの

import Foundation

func quickSort<Element: Comparable>(array: [Element], startIndex: Int, endIndex: Int, priorityFunction: @escaping (Element, Element) -> Bool) -> array {
    var order = 0
    var array = array
    if startIndex >= endIndex {
        return order
    }
    let pivot = priorityFunction(array[startIndex], array[startIndex + 1]) ? array[startIndex] : array[startIndex + 1]
    let tupple = partition(array: array, startIndex: startIndex, endIndex: endIndex, pivot: pivot, priorityFunction: priorityFunction)
    array = tupple.array
    let index = tupple.index
    order += tupple.order
    quickSort(array: array, startIndex: <#T##Int#>, endIndex: <#T##Int#>, priorityFunction: <#T##(Comparable, Comparable) -> Bool#>)
}

func partition<Element: Comparable>(array: [Element], startIndex: Int, endIndex: Int, pivot: Element, priorityFunction: @escaping (Element, Element) -> Bool) -> (array: [Element], index: Int, order: Int) {
    var order = 0
    var array = array
    var startIndex = startIndex
    var endIndex = endIndex
    while true {
        while array[startIndex] < pivot { startIndex += 1; order += 1}
        while array[endIndex] >= pivot { endIndex += 1; order += 1 }
        if startIndex > endIndex { return (array, endIndex, order) }
    }
    array.swapAt(startIndex, endIndex)
}

var array = [5, 6, 3, 9, 2, 8, 4, 7]