四十三庵

蔀の雑記帳

Bubble Sort(バブルソート)

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

  • 小さな泡が水から浮き上がるようにソートすることから
  • 「配列の最後からその一個前の要素を大小比較して、逆だったら要素を入れ替える」という操作を最初の要素の一個前まで行うことで最小の要素が配列の最初になる
    • その操作を次は最初の要素の二個前まで行う
    • その操作をn-1番目まで繰り返すと、昇順のソートが完了する
  • 計算量はO(n2)
  • 実装は楽だけど、計算量が最悪なので、絶対に使わないでね、というアルゴリズム

実装

import Foundation

extension Array {
    // 戻り値は計算量を返す
    @discardableResult mutating func bubbleSort(priorityFunction: @escaping (Element, Element) -> Bool) -> Int {
        var order = 0 //計算量
        let n = self.count
        let firstIndex = self.indices.first!
        let lastIndex = self.indices.last!
        for _ in 0..<n {
            for j in stride(from: lastIndex, to: firstIndex, by: -1) {
                order += 1
                if priorityFunction(self[j - 1], self[j]) == false {
                    self.swapAt(j - 1, j)
                }
                
            }
        }
        return order
    }
}

var array = [2, 1]
print(array.bubbleSort(priorityFunction: <)) //2
print(array)

array = [1, 2, 4, 3, 6, 5]
print(array.bubbleSort(priorityFunction: <)) //30
print(array)

array = (1...20).map { $0 }
print(array.bubbleSort(priorityFunction: >)) //380(ざっくり20^2)
print(array)

array = (1...1000).map { $0 }
print(array.bubbleSort(priorityFunction: <)) //999,000(ざっくり1,000^2 = 1,000,000)
print(array)

// 10万回の計算くらいなら一瞬だが、それ超えると厳しい