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

Swift Algorithm Clubさんより。

選択ソート Selection Sort

最初に配列の中から順番に最小値(最大値)を探します。見つけた値と配列の先頭[0]の値と交換します。

先頭[0]は最小値ということがわかったので、[0]は置いといて、次、[1]の値を対象に配列内の数字と比べます。見つかった値を配列の[1]と交換します。

[0]から順番に[1][2][3]・・・と比較交換を行います。これの繰り返しです。

func selectionSort(_ array: [Int]) -> [Int] {
guard array.count > 1 else { return array }  
var a = array                    
for x in 0 ..< a.count - 1 {     
  var lowest = x
  for y in x + 1 ..< a.count {   
    if a[y] < a[lowest] {
      lowest = y
    }
  }
  if x != lowest {               
    a.swapAt(x, lowest)
  }
}
return a
}

最初の条件として、

guard array.count > 1 else { return array }

array.countが2以上のもの、配列の数字が2つ以上を対象に並び替えします。

まず、var lowest = x として最小値を設定します。比較対象の数字としては

0 ..< a.count - 1 なのでまず最初は"0"ですね。

ここで最小値は"x = 0"で、"lowest = 0"です。

for y in x + 1 ..< a.count {   
   if a[y] < a[lowest] {
     lowest = y
   }
 }

yが最小値"lowest"と比較して小さい値であれば"lowest"を"y"の値にするということで、配列内の数字と比べ一番小さい番号を選択し最小値"lowest"を決める。

いったんループを抜けます。それで

if x != lowest {               
   a.swapAt(x, lowest)
 }

ですね。

x != lowest

の条件、"x"が"lowest"が同じでなければ、という条件のもと、のもと、

a.swapAt(x, lowest)   

なので　"a"の配列の"x"と"lowest"の値を入れ替えします。

"swapAt(a,b)"はSwiftが最初から持っている便利な関数です。aとbを入れ替えます。

基本この繰り返しです。"x = 0"が終われば、次は"x = 1"という感じで比較対象を変えていきます。元の配列の数字を左から順番に比較して行きます。

[0] →[1]→[2]→[3]→[4]

最後まで行ったら

return a

ということで並び替えした配列を元の配列"a"に入れて終わりです。

試してみましょう！

var result = selectionSort([4,1,7,5])
print(result)　

コンソールに [1, 4, 5, 7]と表示されます。