Rubyでバブルソートを表現してみよう

ryoです。三日坊主してると思いました？自分も思ってました。
unityのアプリを作ってたのですが、自分で理解できなくて、アウトプット出来ないんです。すみません。
バブルソートというものを勉強したのでRailsで表現できるように挑戦しようと思います。

この記事を見て身につくこと

・バブルソートの意味がわかる
・Rubyでバブルソートを表現できる

　目次

• そもそもバブルソートって何？
• バブルソートのルールと手順
• 完成コード
• 各行のコード解説
• その他のソートの種類
• 実は・・・

そもそもバブルソートって何？

バブルソートとは、ソートアルゴリズムの一つです。
ソートアルゴリズムとは、データを整列するための方法みたいものです。ソートというのが整列という意味なので、そのままです。

ではバブルソートとは、どうやってデータを整列していくものかについて見ていきます。

バブルソートの手順、ルール

• 先頭の要素'A'と隣り合う次の要素'B'の値を比較する
• 要素'A'が要素'B'より大きいなら、要素'A'と要素'B'の値を交換する
• 先頭の要素を'B'に移し、要素'B'と隣り合う要素'C'の値を比較/交換する
• 先頭の要素を'C','D','E'...と移動しながら比較/交換をリストの終端まで繰り返す
• 最も大きい値を持つ要素がリストの終端へ浮かびあがる
• リストの終端には最も大きな値が入っているので、リストの終端の位置をずらして(要素数をひとつ減らして)
• 上記手順を繰り返す

ここの手順を引用させてもらいましたイメージ図もこちらにあります。

完成コード

test.rb

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内は呼び出されるまで動かないので一旦下から読み始めます。

まずは数値を入力してもらいます。

test.rb

puts "整列させる数値を入力してください"
bubblesort(gets.chomp)

入力した数値をbubblesort内に持っていって色々します。

test.rb

def bubblesort(int)

入力されたものをcharsで１文字ずつに分割してmapで数値に変更します

test.rb

  datas = int.chars.map(&:to_i)

文字の数だけ繰り返す記述です。

test.rb

  datas.length.times do |data|

１文字ずつ処理するための記述です。２文字目、３文字目になるにつれて右側の数値が確定していくので、
確定した文字分処理を減らします。

test.rb

    (datas.length - (data + 1)).times do |array|

整列させる数値を入力してください
94783 #入力
49783
47983
47893
47839　＃この時点で一番右は確定しているから比較する必要がなくなる。

現在の要素と、次の要素を比較して現在の要素が大きいか確認します。

test.rb

        if datas[array] > datas[array + 1]

大きかった時は、要素を入れ替えます。

test.rb

            datas[array],datas[array + 1] = datas[array + 1],datas[array]

整列させる数値を入力してください
94783 #入力
49783 #９と４を比べて、９の方が大きいから入れ替えている

ばらけさせてる数字を連結させます。処理の動きがわかりやすいようにtimes内に入れてますが
結果だけを知りたい場合はもっと下のendに下記記述を移動すれば結果だけ出るようになります。

test.rb

        puts datas.join

その他のソートの種類

• バケットソート（ビンソート）
• 基数ソート
• ヒープソート
• マージソート（併合ソート）
• クイックソート 等、色々あります。

実は・・

今回は動きがわかりやすいように
コードを紹介しましたが、ソートは各言語で簡単にできるようになっているんです。

rubyの場合sortというものがあるので、下記でソートは完了してしまいます。便利ですね。

test.rb

def bubblesort(int)
  datas = int.chars.map(&:to_i)
  datas.sort!
  puts datas.join
end

puts "整列させる数値を入力してください"

bubblesort(gets.chomp)

出力結果

整列させる数値を入力してください
956217329 #入力
122356799

だから、普段はあんまり意識する必要ないけど、バブルソートってどんなんだろう？って思った時に思い出してあげてください。お疲れ様でした。