バブルソートについて

バブルソートのアルゴリズムをRubyを使い学んでいく。

某プログラミングスクールのアルゴリズムのカリキュラムを、
修理しているノートPCが返ってくる前に終わらせられそうです。

バブルソートとは？
整列アルゴリズムの１つで配列の隣り合う
データの大小を比較して並べる。
バブルソートを使用した整列は末尾の比較と交換からスタート。
数字が正しく整列できていなければ交換を行い、
先頭の方向に向かいながら順に整列を行う。
先頭には比較をすべての要素と行った後の要素が来るので、
整列できていると確定する。
繰り返し処理、二重ループを使い実装していく。

例
[11,45,55,22,33]→[11,44,55,22,33]→[11,44,22,55,33]→
[11,22,44,55,33]→[11,22,44,33,55,]→[11,22,33,44,55]

バブルソートのポイントは
・二重ループ
・変数同士の値の交換方法
・交換回数を意識した二重ループの範囲指定方法

例題

def bubble_sort(ary)
  (1...ary.length).each do |i|
    (i...ary.length).reverse_each do |j|
      if ary[j -1] > ary[j]
        tmp = ary[j - 1]
        ary[j - 1] = ary[j]
        ary[j] = tmp
      end
    end
  end
  return ary
end

ary = [245,45,32,367,122,67,14,89]
p ary
p bubble_sort(ary)

解説
ary配列の定義

p bubble_sort(ary)

で関数の呼び出し

(1...ary.length).each do |i|

で繰り返し処理を実行する。
1...ary.lengthは配列の要素分、変数iは各要素のインデックスを取得。
このループは、配列の要素の数より1少ない回数繰り返されます。

(i...ary.length).reverse_each do |j|

reverse_eachで配列の後ろから処理を開始できるようになる。
変数jは現在比較交換をしようとしている要素を選択している。
つまり最初のループでは89を選択している。

if ary[j -1] > ary[j]

各ループ内で隣接する要素を比較します。
この場合左隣が大きければif構文が発生するようにします。

tmp = ary[j - 1]
ary[j - 1] = ary[j]
ary[j] = tmp

if隣接する要素の方が大きい場合if処理が発生し、
要素の交換を行います。
交換する場合一時的な変数 tmp を使用して、
要素を交換します。
具体的には、ary[j - 1] の値を tmp に保存し、
ary[j - 1] に ary[j] の値を代入し、
最後に ary[j] に tmp の値を代入します。

最後にreturn aryで整列された配列を返却処理しましょう。
これで配列aryの要素を並び替える実装ができました。

(i...ary.length).reverse_each do |j|の変数iにする訳は？

さて内側のループはなぜ(1...ary.length)ではないのか
１にすると確定した要素も比較対象に入ってしまうからです。
１週目のループで要素14が一番左に行きます。
しかし２回目のループを行う際確定している14を
比較するのは無駄になってしまいます。
変数iが１の時、.reverse_eachで行うソートで最小値14が確定します。
２週目の際には変数iは２になります。
最小値14は1にあるので14は除外されます。

ここからはさらに詳しく、１回目の内側のループの処理について深堀。

ary = [14,245,45,32,367,122,67,89]
(1...ary.length).each do |i|
  (i...ary.length).reverse_each do |j|
   if ary[j -1] > ary[j]
      tmp = ary[j - 1]
      ary[j - 1] = ary[j]
      ary[j] = tmp
    end
  end

で末尾から繰り返し比較していく、まず89と14を比較してifは起こらない
次に末尾から２つ目14と67を比較して初めてifが起こり、要素の交換が起こります。
配列の中身は[245,45,32,367,122,14,67,89]になる。
次に末尾から３つ目14と122を比較してifが起こり、要素の交換が起こる。
配列の中身は[245,45,32,367,14,122,,67,89]になる。
次に末尾から4つ目14と347を比較してifが起こり、要素の交換が起こる。
配列の中身は[245,45,32,14,367,122,,67,89]になる。
次に末尾から5つ目14と32を比較してifが起こり、要素の交換が起こる。
配列の中身は[245,45,14,32,367,122,,67,89]になる。
次に末尾から6つ目14と45を比較してifが起こり、要素の交換が起こる。
配列の中身は[245,14,45,32,367,122,,67,89]になる。
次に末尾から7つ目14と245を比較してifが起こり、要素の交換が起こる。
配列の中身は[14,245,45,32,367,122,,67,89]になる。
これで内側のループが終わり１回目の外側のループが終わる。

では外側の２回目のループを深堀していく、

もう理解しているという人は見る必要はないですね。

ary = [14,245,45,32,367,122,67,89]
(1...ary.length).each do |i|
  (i...ary.length).reverse_each do |j|
   if ary[j -1] > ary[j]
      tmp = ary[j - 1]
      ary[j - 1] = ary[j]
      ary[j] = tmp
    end
  end

外側のループは２回目ですね.
内側のループは今の配列に注目して下さい。
(i...ary.length)は２回目のループなので実質(2...ary.length)
になり配列の先端14はソートから除外されます。
まず89と67を比較してifは起こらないし配列の変化なし
次に末尾から２つ目67と122を比較してifが起こり、要素の交換が起こる。
配列の中身は [14,245,45,32,367,67,122,89]になる。
次に末尾から3つ目67と367を比較してifが起こり、要素の交換が起こる。
配列の中身は [14,245,45,32,67,367,122,89]になる。
次に末尾から4つ目67と32を比較してifは起こらないし配列の変化なし。
配列の中身は [14,245,45,32,67,367,122,89]になる。
次に末尾から5つ目32と45を比較してifが起こり、要素の交換が起こる。
配列の中身は [14,245,32,45,67,367,122,89]になる。
次に末尾から6つ目32と245を比較してifが起こり、要素の交換が起こる。
配列の中身は [14,32,245,45,67,367,122,89]になる。

２回目のループなので先頭の14は比較から除外されています。
重要なのは67の比較と32の比較でifが起こっていない点です。
交換が行われなくても繰り返し処理は続くので
比較する数字が変わり67→32になります。

後は同じことの繰り返しを行うだけです。
アルゴリズムの勉強は難しいと思います。
例題を解くだけなら簡単ですが、
こうして記事に書いていく、自分なりの言葉で
解説していくほうが何倍も時間がかかります。
アルゴリズムの勉強は成果が出るわけでもないですが、
実力のある人はこういった勉強もしているのでしょうか。
あとこの記事の内容が間違っていたら申し訳ありません。