Swiftでいこう -- アルゴリズムでいこう。3

Swift Algorithm Clubさんより。

挿入ソート Insertion Sort

挿入ソートは配列の整列済みの部分に対して新たな要素を適切な位置に挿入することで整列を行うアルゴリズムです。

挿入ソートは常に隣り合う要素で比較、交換を行います。

func insertionSort(_ array: [Int]) -> [Int] {
var a = array	
for x in 1..<a.count {	
var y = x
while y > 0 && a[y] < a[y - 1] { 
a.swapAt(y - 1, y)
y -= 1
}
}
return a
}

for x in 1..<a.count で"x"に1から配列の数だけ順番に入れて行きます。

例えば次のような配列で整列をやってみましょう。

insertionSort([4,1,7,5])

for x in 1..<a.count {}　ということでまず、"x"には"1"が入ります。

var y = x

なので"y"が"1"となり、var a = array なので、

while y > 0 && a[y] < a[y - 1] { 
a.swapAt(y - 1, y)
y -= 1
}

のコードが実行されるとa[y] はa[1]、a[y - 1]はa[0]がはいります。

配列"a"の数字は

a[1]は"1"、a[y - 1]は"4"

なので　y > 0 && a[y] < a[y - 1]　に該当するので

a.swapAt(y - 1, y)　// y - 1と yを入れ替えます

次に

y -= 1　// yの値を1減らします

この作業を

while y > 0 && a[y] < a[y - 1]

なので条件に該当すれば、繰り返します。

for x in 1..<a.count{}　

の中に

while y > 0 && a[y] < a[y - 1]{}　がある形です。

"x"の値が1,2,3・・と取り出されます。その数値をもとに

まず、a[1]が

while y > 0 && a[y] < a[y - 1]{}の条件で処理をされます。条件が満たされなくなるとされ一旦終わります。

次にa[2]がスタートします。この繰り返しを"a.count"、配列の数だけ繰り返します。[4,1,7,5]の配列ですと4回繰り返します。

while y > 0 && a[y] < a[y - 1]{ }

の中で入れ替えをしていきます。

Selection Sort(選択ソート)は前から順番に決めていく。先頭のものと他の数字全てを見比べて、先頭から決める。

Insertion Sort(挿入ソート)は前から順番に並び替えをする。まず、前 2つの数字、[0],[1]を比べて並び変える、次に[0],[1],[3]までの並び替えをするというふうに処理を行う。

Selection Sortは配列全体を調べて並び替え、に対してInsertion Sortは限定的に小さい範囲で並び替えをしていき最終全ての配列の並び替えをする。

Selection SortよりInsertion Sortのほうが処理速度は早いとされます。限定的に小さい範囲で並び替えをするほうが無駄が最小限に抑えらるからでしょうか。

ソートのアルゴリズムは分割、限定することにより早くなる感じですね。