【algorithm】シェルソート、クイックソート

はじめに

今回はシェルソートとクイックソートを紹介したいと思います！

シェルソート

間隔を空けて挿入ソートを行い、その間隔をだんだん狭めていく方法
特徴は
・少ないデータであればソートは高速になる
・大雑把でも順番に並んでいる部分が多いと挿入ソートは高速にソートできる
考え方として、
・グループ分けの間隔を半分にしていく繰り返しを行う
・その中で各グループに対して挿入ソートを行う

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

クイックソート

少し難しいです。
配列の中の小さいデータを左に集め、大きいデータを右に集め、大小二つのグループに分けます。それぞれのグループで同様に左に小さい、右に大きいデータを集め、二つのグループに分ける。これを繰り返していくと、最終的にソートされた配列が完成します。
・真ん中にある値を基準にしてデータを大小二つのグループに分割する
・分割したグループのそれぞれに同じ処理を繰り返す。
・交換回数を減らすために交換する必要があるものだけで交換を行う
・アルゴリズムをシンプルにするために、再帰を使う
ちなみに、基準となる値をピボットと言います。
「再帰」とは、自分で自分自身を呼び出すアルゴリズムです。
今回は分割した部分に対してさらに分割して同じような処理をしていくという階層的な繰り返しになっているので、このような回想的な繰り返しには再帰を使います。

var nums = [5, 3, 14, 15, 7, 9, 13, 1, 2, 4, 12, 11, 8, 6, 10]
func quickSort(startID: Int, endID: Int) {
    let pivot = nums[Int((startID + endID) / 2)]
    var left = startID
    var right = endID
    while true {
        while nums[left] < pivot {
            left += 1
        }
        while pivot < nums[right] {
            right -= 1
        }
        if right <= left {
            break
        }
        let t = nums[left]
        nums[left] = nums[right]
        nums[right] = t
        left += 1
        right -= 1
    }
    if startID < left - 1 {
        quickSort(startID: startID, endID: left - 1)
    }
    if right + 1 < endID {
        quickSort(startID: right + 1, endID: endID)
    }
}
quickSort(startID: 0, endID: nums.count - 1)
print("ソート後:", nums)
// ソート後: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

おわりに

次回から応用的なアルゴリズムをみていきます！