【algorithm】単純交換法、単純選択法、単純挿入法

はじめに

今回は整列(ソート)アルゴリズムについてまとめていこうと思います！

単純交換法(バブルソート)

全ての隣り合った値を比べていき、小さい方が前に移動するように交換する方法
総当たりてきなアルゴリズムなので、大量データには向かない

var nums = [5, 3, 7, 9, 1, 2, 4, 8, 6]
for i in 0..<nums.count  {
    for j in stride(from: nums.count-1, to: i, by: -1) {
        if nums[j] < nums[j-1] {
            let t = nums[j]
            nums[j] = nums[j-1]
            nums[j-1] = t
        }
    }
}
print("ソート後:", nums)
// ソート後: [1, 2, 3, 4, 5, 6, 7, 8, 9]

まず、前からソート済みを省いた要素にアクセスするためfor文と後ろから二つを比較して行くためのfor文の二つのfor文が必要です。
stride(from: nums.count-1, to: i, by: -1)で配列を逆順でアクセスできます。
あとは、二つを比較していき、左の方が大きい場合は交換のアルゴリズムを使って交換します。交換のアルゴリズム

単純選択法(選択ソート)

最小値を探して先頭から順番に並べていく方法
最小値をを入れる位置を「選択」し、最小値と交換していくので、選択ソートという
最小値と交換のアルゴリズムを使います。最小値のアルゴリズム, 交換のアルトリズム

var nums = [5, 3, 7, 9, 1, 2, 4, 8, 6]
for i in 0..<nums.count {
    var min = nums[i]
    var k = i
    for j in (i+1)..<nums.count {
        if min > nums[j] {
            min = nums[j]
            k = j
        }
    }
    let t = nums[i]
    nums[i] = nums[k]
    nums[k] = t
}
print("ソート後:", nums)
// ソート後: [1, 2, 3, 4, 5, 6, 7, 8, 9]

ポイントは、最小値の位置を表す変数も用意してその位置を保存しておくことです。

単純挿入法(挿入ソート)

データを抜き出して正しい位置に挿入していく方法
・整列していない部分から挿入する値を順番に一つずつ取り出す繰り返しをする
・その中で取り出した整列した部分のどこに挿入すればよいかをみていく繰り返しをする

var nums = [5, 3, 14, 15, 7, 9, 13, 1, 2, 4, 12, 11, 8, 6, 10]
for i in 1..<nums.count {
    let t = nums[i]
    var insert = 0
    for j in stride(from: i-1, through: 0, by: -1) {
        if nums[j] > t {
            nums[j+1] = nums[j]
        } else {
            insert = j + 1
            break
        }
    }
    nums[insert] = t
}
print("ソート後:", nums)
// ソート後: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

おわりに

今回は単純なソート方法を紹介しました！次回は少し難しいシェルソートとクイックソートについてまとめていこうと思います！