【学習ログ】【Ruby】バブルソート(単純交換法) プログラム

※このページは過去に自分がRubyの勉強をしたときの学習ログです。誰かの参考になれば幸いです。

バブルソート(単純交換法) プログラムをRubyで作成してみた

完成コードの前にバブルソートとは何かを考える

バブルソートはリストにおいて隣り合うふたつの要素の値を比較して条件(大小関係)に応じた交換を行うアルゴリズムのこと。

こちらも以下の動画が参考になった。

完成コード

# バブルソート(単純交換法)
def bubble_sort(numbers)
  
  for i in 0..((numbers.length)-1) 
     
    for j in 1.. ((numbers.length)-i-1)
      if numbers[j-1] > numbers[j]
        numbers[j-1],numbers[j] = numbers[j],numbers[j-1]
      end
    end
  end
  numbers
end

p bubble_sort([100,50,25,4,1])

実行結果 →[1, 4, 25, 50, 100]

解説(我流です)

選択ソートと比較するとやや飲み込みやすかったが、
こちらも複雑で解説できるレベルではない・・

最初のfor i in 0..((numbers.length)-1)と、
for j in 1.. ((numbers.length)-i-1)について深掘りしてみた。

まず、for i in 0..((numbers.length)-1)については要素の数だけ繰り返しをするよ!という意味のループ処理でいわば繰り返しの数を意味する。
一方で、for j in 1.. ((numbers.length)-i-1)は何回隣の要素とチェックを行うかという意味のコード。

上の例ではjは1から始まり、配列の個数(5)-1で、要素番号[4]までチェックするよ〜ということになるが、1回目の処理で右端が最大値であることが決まるため、2回目の処理は要素番号[4]と比較する必要がなく、要素番号[3]までをチェックすれば良い。
つまり繰り返される度に処理回数を減らすためのコードがfor j in 1.. ((numbers.length)-i-1)となる。

また、numbers[j-1] > numbers[j]とする理由について、
numbers[j] > numbers[j+1]とかにしてしまうと、
最後の要素が[4] に対して、+1だと配列の範囲を超えてしまうためエラーとなってしまう。
(要素番号[5]は存在しないため)

こちらについても流れについては以下の動画の解説がわかりやすかった。
言語は異なるが、概ね解釈は同じだと思うので・・

本日は以上となります。

最後までお読みくださりありがとうございました。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

コメントする