ryoです。三日坊主してると思いました?自分も思ってました。
unityのアプリを作ってたのですが、自分で理解できなくて、アウトプット出来ないんです。すみません。
バブルソートというものを勉強したのでRailsで表現できるように挑戦しようと思います。
この記事を見て身につくこと
・バブルソートの意味がわかる
・Rubyでバブルソートを表現できる
## 目次
- そもそもバブルソートって何?
- バブルソートのルールと手順
- 完成コード
- 各行のコード解説
- その他のソートの種類
- 実は・・・
そもそもバブルソートって何?
バブルソートとは、ソートアルゴリズムの一つです。
ソートアルゴリズムとは、データを整列するための方法みたいものです。ソートというのが整列という意味なので、そのままです。
ではバブルソートとは、どうやってデータを整列していくものかについて見ていきます。
バブルソートの手順、ルール
- 先頭の要素'A'と隣り合う次の要素'B'の値を比較する
- 要素'A'が要素'B'より大きいなら、要素'A'と要素'B'の値を交換する
- 先頭の要素を'B'に移し、要素'B'と隣り合う要素'C'の値を比較/交換する
- 先頭の要素を'C','D','E'...と移動しながら比較/交換をリストの終端まで繰り返す
- 最も大きい値を持つ要素がリストの終端へ浮かびあがる
- リストの終端には最も大きな値が入っているので、リストの終端の位置をずらして(要素数をひとつ減らして)
- 上記手順を繰り返す
ここの手順を引用させてもらいましたイメージ図もこちらにあります。
完成コード
def bubblesort(int)
datas = int.chars.map(&:to_i)
datas.length.times do |data|
(datas.length - (data + 1)).times do |array|
if datas[array] > datas[array + 1]
datas[array],datas[array + 1] = datas[array + 1],datas[array]
end
puts datas.join
end
end
end
puts "整列させる数値を入力してください"
bubblesort(gets.chomp)
出力結果
整列させる数値を入力してください
94783 #入力
49783
47983
47893
47839
47839
47839
47389
47389
43789
34789
各行のコード解説
def内は呼び出されるまで動かないので一旦下から読み始めます。
まずは数値を入力してもらいます。
puts "整列させる数値を入力してください"
bubblesort(gets.chomp)
入力した数値をbubblesort内に持っていって色々します。
def bubblesort(int)
入力されたものをcharsで1文字ずつに分割してmapで数値に変更します
datas = int.chars.map(&:to_i)
文字の数だけ繰り返す記述です。
datas.length.times do |data|
1文字ずつ処理するための記述です。2文字目、3文字目になるにつれて右側の数値が確定していくので、
確定した文字分処理を減らします。
(datas.length - (data + 1)).times do |array|
整列させる数値を入力してください
94783 #入力
49783
47983
47893
47839 #この時点で一番右は確定しているから比較する必要がなくなる。
現在の要素と、次の要素を比較して現在の要素が大きいか確認します。
if datas[array] > datas[array + 1]
大きかった時は、要素を入れ替えます。
datas[array],datas[array + 1] = datas[array + 1],datas[array]
整列させる数値を入力してください
94783 #入力
49783 #9と4を比べて、9の方が大きいから入れ替えている
ばらけさせてる数字を連結させます。処理の動きがわかりやすいようにtimes内に入れてますが
結果だけを知りたい場合はもっと下のendに下記記述を移動すれば結果だけ出るようになります。
puts datas.join
その他のソートの種類
- バケットソート(ビンソート)
- 基数ソート
- ヒープソート
- マージソート(併合ソート)
- クイックソート
等、色々あります。
実は・・
今回は動きがわかりやすいように
コードを紹介しましたが、ソートは各言語で簡単にできるようになっているんです。
rubyの場合sortというものがあるので、下記でソートは完了してしまいます。便利ですね。
def bubblesort(int)
datas = int.chars.map(&:to_i)
datas.sort!
puts datas.join
end
puts "整列させる数値を入力してください"
bubblesort(gets.chomp)
出力結果
整列させる数値を入力してください
956217329 #入力
122356799
だから、普段はあんまり意識する必要ないけど、バブルソートってどんなんだろう?って思った時に思い出してあげてください。お疲れ様でした。