🛁

【Ruby】バブルソートをfor文で解きたい

2022/03/28に公開約2,100字

バブルソートとは

バブルソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート(整列)アルゴリズムの最も基本的な手法の一つで、端から順番に隣接する要素同士を比較・交換していくもの。

列の一方の端から反対の端まで順番に行うことが多く、繰り返しの度に未整列の要素の中で最も大きな(あるいは小さな)要素が列の端に移動していく様子を泡(バブル)が浮き上がっていく様に例えてこのような名称となったそうです。

何やってるかイメージできない

後述する練習問題をやった後に見つけた動画ですが、処理で行われていることのイメージがとても分かりやすかったです。有難い・・・
人工バブルソート

練習問題

問題

以下の要件を満たすbubble_sortメソッドを実装しましょう。
要素が数値である配列を受け取り、数値の小さい順に並べ替えること
小さい順に並べ替えた結果を出力すること

雛形

def bubble_sort(data)
  # 配列の数を数える処理を記述
  length = 

  # for文を2つ使用する
  # 先頭から隣の数同士の大きさを比べる
  # 先頭側の要素の方が大きい場合は、配列の位置を隣同士で交換する
end

呼び出し例

number = [1,23,4,6,12,45,79]
bubble_sort(number)
puts number

私の回答

def bubble_sort(data)
  length = data.length

  for i in 0..length-1
    for j in i..i+1
      if data[j] > data[j+1]
        data[j], data[j+1] = data[j+1], data[j]
        return data
      end
    end
  end
end

模範回答

def bubble_sort(data)
  length = data.length 
  for i in 0..(length-1) 
    for j in 1.. (length-i-1) 
      if data[j-1] > data[j] 
        data[j-1],data[j] = data[j],data[j-1] 
      end
    end
  end
end

解説

2行目で、配列dataの要素の数をカウントし、その結果を変数lengthに代入しています。

3行目の親のfor文では、配列dataの要素の数だけ処理が繰り返されるように設定しています。
変数iには、配列の要素の位置番号が順に代入されます。配列の要素は先頭を0番目とカウントするので「length(配列の要素の数)-1」となっていることに注意です。

4行目の子のfor文では、親のfor文の処理回数に関連して、処理が繰り返されるように設定しています。

親のfor文が1回目の時は、変数jに1から6までの数字が順に代入されていきます。(length-i-1)が、7(配列の数)-0(変数i)-1 = 6となるからです。
親のfor文が2回目の時は、変数jに1から5までの数字が順に代入されていきます。(length-i-1)が、7(配列の数)-1(変数i)-1 = 5となるからです。

繰り返し処理の内容について説明します。
5行目では、配列の先頭から順に隣同士の数の大きさを比較しています。if文は「隣同士の数を比べて、前の数の方が大きければ」という条件になっています。
6行目では、if文の条件に当てはまった場合のみ、配列の位置を交換しています。

感想

私の回答だと処理が1回きりで終わってしまって、かつreturn dataで返してしまっていました。
あと、まずかったのは`j+1`というのを使っていました。
lengthは決まっているのにlengthよりも大きい数字が入ってしまうのは良くないですね。

親のfor文に注目すると、1回目で一番大きな数字を確定させ(右端によせる)、2回目で二番目に大きな数字を確定(右から二番目に寄せる)という流れであることを理解できました。

参考

バブルソートは他にもたくさん記述方法があるようです。
(for文とeach文の使い分けって何が違うのだろう・・?)
メソッドやコードは違いますが、こちらの記事も分かりやすくて参考になりました。

https://www.y-hakopro.com/entry/bubble_sort
https://programming-beginner-zeroichi.jp/articles/286

Discussion

ログインするとコメントできます