ちょっとアルゴニズム　- Insertion Sort(Swift)

挿入ソートです。

挿入ソート : アルゴリズム

日本語で解説してあります。

ではswift-algorithm-clubで紹介されているものをやっていきます。

raywenderlich/swift-algorithm-club

例えばということで

"8, 3, 5, 4, 6"という配列を並び替えしていきます。挿入ソートということで一番最初の数字、ここでは"8"をまず対象にします。その次に"8,3"を対象にします。これを続けて"6"までやるとソート完了となります。

コードです。

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
} 

関数を作っています。引数を配列で受けて、ソートしていきます。

func insertionSort(_ array: [Int]) -> [Int] {
}

関数名 insertionSort() 引数、"_ array: [Int]"配列を整数を渡します。あとは内部処理です。

引数のarrayは変更不可なので変数"a"を作ってその後の作業に続きます。

 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  in 文ですが、ここでも"1..<a.count"で取り出した数字も新たに変数"y"に入れて,その後の処理に使います。

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

"y"は0以上で配列の一つ前(a[y - 1] )より大きければ

a.swapAt(y - 1, y)

入れ替える。という操作を、操作が終わるたびに"y > 0"の範囲内(While)で

y -= 1

を実行します。

この仕組みを図示してみます。