Rubyを使ったアルゴリズムについて学習しています。
今回は数字の配列を並べ替える方法についてやっていきます。
やりたいこと
sortメソッドを利用せず、数字の配列を昇順ソートして出力するアルゴリズムを作成する。
array = [6, 7, 3, 2, 5, 4, 1]
これを、こうしたい。
array = [1, 2, 3, 4, 5, 6, 7]
バブルソートとは？
値を昇順・降順で並べ替えるアルゴリズムのひとつ
pointデータを小さい順（大きい順）に並べ替えるよ
point隣り合う要素の大小比較を繰り返すことで、全体を並べ替えるよ
引用：バブルソートとは｜「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典
まずは数字の並べ替えるプログラムを作る
# 配列を定義
array = [6, 7, 3, 2, 5, 4, 1]
if array[2] > array[3] # 配列は0からはじまるのが注意点
# 一度、変数に退避した後、入れ替える
escape = array[3] # => escape = 2となる
array[3] = array[2] # => array[3] = 3となる
array[2] = escape # => array[2] = 2となる
end
p escape # => 2
p array[2] # => 2
p array[3] # => 3
p array # => [6, 7, 2, 3, 5] これでarray[2]とarray[3]が入れ替わった。
- 配列は0からはじまるのが注意点です。
- 一度、別の変数に退避した後、入れ替えます。
最終的な完成コード
array = [6, 7, 3, 2, 5, 4, 1]
array_size = array.size
array_size.times do |i|
(array_size - (i + 1)).times do |j|
if array[j] > array[j + 1]
escape = array[j]
array[j] = array[j + 1]
array[j + 1] = escape
end
end
end
p array
出力結果
[1, 2, 3, 4, 5, 6, 7]
完成コードの解説
-
array = [6, 7, 3, 2, 5, 4, 1]まずは配列を定義する。 -
array_size = array.sizeで配列の要素数を取得し、変数に代入する。 -
array_size.times do |i|で、比べる数の要素分をループ処理する。 -
(array_size - (i + 1)).times do |j|は、比べられる残りの要素分をループ処理する。この時、iの初期値は0のため(i + 1)にして残りの配列の要素の個数を計算していることに注意する。 -
if array[j] > array[j + 1]からのif文では、隣同士の数値を比較し、左の数のが大きい場合、配列内の数値の位置を入れ替える処理を定義する。 -
array[j]は左側の数字、array[j + 1]は右側の数字として、左右を比べている。 - 最後に
p arrayで出力する。
まとめ
sortメソッドを使えば簡単なわけですが、その中身を理解することで、後々、応用が効くようになったりするのかなぁと思います。
他にもfor文を使ったバブルソートなど、いくつかの方法があるようです。
参考サイト：
バブルソートとは｜「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典
Rubyによるバブルソートアルゴリズム
【Ruby】バブルソートをfor文で解きたい