2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2019-10-31

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で1文字ずつに分割してmapで数値に変更します

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

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

test.rb
  datas.length.times do |data|

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

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 #9と4を比べて、9の方が大きいから入れ替えている

ばらけさせてる数字を連結させます。処理の動きがわかりやすいように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

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

2
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?