Ruby バブルソート

質問

バブルソートのプログラムでわからないところがあるため、
質問させていただきます。

Rubyは1.9.3を使用しています。

＜プログラム＞
---------------------------------------------------
def bsort(data)
　　while true
　　　　# swapped変数は数値の入れ替えを記憶
　　　　swapped = false
　　　　for i in 0..data.size-2
　　　　　　if data[i] > data[i+1]
　　　　　　　　temp = data[i]
　　　　　　　　data[i] = data[i+1]
　　　　　　　　data[i+1] = temp
　　　　　　　　swapped = true
　　　　　　end
　　　　end
　　　　return if !swapped
　　end
end

data = [10, 9, 8, 7, 6]
bsort(data)
puts "ソート結果#{data}"

---------------------------------------------------

return if !swapped のところで、
なぜwhileのループから抜けられるのかがよくわかりません。
return if swapped == false
と書き換えて実行しても同じ結果が得られたのですが、
数値の入れ替えがなければ　swapped = false　であるため、
!swappedはtrueとはならないのでしょうか。

回答No.8

kmee

そういうことでしたか。
whileの件は誤解が解けたようなので。

バブルソートは「隣同士の値を比べて、順位が逆なら入れかえる」を繰り返して、整列させるアルゴリズムです。
値に注目すると、それが泡が浮んでいくように徐々に移動するので「バブルソート」という名前が付いています。

入れ替えが発生すると、その前後の上下関係が変わってしまうことがあります。
ですから、もう一度全体を調べます。

入れ替えが発生しなかった、ということは、全ての箇所で順番通り、という意味です。
ということは、並び換えが完了している、ということです。
並び換えが終了したなら、処理を続ける必要はありません。

正月ですし、トランプが手許にあったら、次の指示通りにやってみましょう。

トランプの同じマークの一セットとジョーカーを用意します。
適当に混ぜたら、裏返しで横に並べます。(左から0,1,2,3..12とします)
※
ジョーカーを裏にします
0,1を表にします。
　0の方が大きかったら2枚の位置を入れ替えます。ジョーカーを表にします。
0,1を裏返します。
1,2を表にします。
　1の方が大きかったら2枚の位置を入れ替えます。ジョーカーを表にします。
1,2を裏返します。
...(略)
11,12を裏返します。
ジョーカーが裏のままなら終了です。
そうでなければ、※から繰り返します。

全部表にしたら、どんな風に並んでいるでしょうか

お礼

再度回答いただきありがとうございます。

実際にトランプでバブルソートを試してみました。
全部表にしたらAからKまで左から順に並んでいました。
ジョーカーは裏になっています。
このトランプではジョーカーがswappedの役割を果たしているのですね。
実際にトランプで試してみると、バブルソートの仕組みが理解しやすく、
勉強になりました。
何度も回答いただきまして改めて感謝申し上げます。

回答No.7

siffon9

No.4です。

> return if !swapped　の!swappedで、
> なぜ入れ替えを行わなかった場合、つまりswapped == falseの時のみ、
> returnでbsortを終了するのかについても教えていただけますでしょうか。

return if !swapped　は以下の様に書き直せます。

if swapped == false
　return
end

if文の動作はご存知だと思いますが、
swapped==falseの時にreturnが実行されます。
その場合には、メソッドbsortを終了します。

swappped==trueの場合はreturnが実行されません。
その場合は、while(true) ～ end のループを繰り返すことになります。
従ってwhileループが終了しないのでメソッドbsortを終了しません（下の※C点に到達しない）

以下に元のメソッドの簡略版を書いてみましたご理解の一助にしていただければ幸いです。

def bsort(data)
　　while true　　　# ループ条件が常に真なのでwhile～endを無限ループする
　　　　　　　　　　# (※A)
　　　　swapped = false
　　　　if 数値の入替があった場合
　　　　　swapped = true # この場合は※Bでメソッドを終了しない
　　　　end

　　　　if swapped==false
　　　　　return　　#　(※B) ここでメソッドを終了する（swappedがfalseの場合)
　　　　end
　　end 　　　　　　# 無限ループなので※Aに戻る

　　　　　　　　　　#　(※C) swapped==trueの場合はここに到達しない
end

お礼

再度回答いただきありがとうございます。

>return if !swapped　は以下の様に書き直せます。

if swapped == false
　return
end

このように記述していただけると理解できました。
また、メソッドの簡易版のプログラムも教えていただき、
大変わかりやすく勉強になりました。
別の回答者様の御礼コメントにも書かせていただきましたが、
>否定(NOT)は演算子「!」の右辺の条件式が真の場合に全体の式の評価が偽となり、右辺の条件式が偽の場合に全体の式の評価が真となります。
とサイトに書かれていたのですが、
全体の式の評価というのがよくわかっておらず、
return if !swapped　の部分が理解できませんでしたが、
今回理解することができました。
何度も回答いただきまして改めて感謝申し上げます。

回答No.6

notnot

Ｎｏ1,3,5です。

＞これは理解しておりましたが、while全体の値はreturnの後ろの値ではないのですね。失礼しました。

return は、whileと関係なく、メソッド定義からその値を持って抜け出します。
whileループの終了条件とか返す値とは次元の違う話です。

＞return if !swapped　の!はswappedの値を真から偽か、偽から真に変更するだけですよね？

swappedの値は変更しませんよ。
return if !swappedは、

work = if swapped
　　　　　　false
　　　　 else
　　　　　　true
　　　　 end

if work
　return
end

みたいな感じです。workが偽の場合はその次の文の実行に移ります。

!swappedと書くとswappedの値が変化すると思っていたなら大きな間違いです。
どこでそんな考えを持ったのか、探った方が良いと思います。

お礼

再度回答いただきありがとうございます。

http://www.rubylife.jp/ini/if/index4.html
このサイトを見ていたのですが、
>否定(NOT)は演算子「!」の右辺の条件式が真の場合に全体の式の評価が偽となり、右辺の条件式が偽の場合に全体の式の評価が真となります。

これを見て、!swappedと書くとswappedの値が変化する、
つまりswappedがfalseならtrueになると思っていたのですが、
(全体の式の評価というのがよくわかっていませんでした)
そうではなくて、swappedがfalseならtrueを返すということなのですね。

>work = if swapped
　　　　　　false
　　　　 else
　　　　　　true
　　　　 end

swappedがtrueならbsortにfalseを返し、
falseならtrueを返すということなのですね。
それで数値の入れ替えを行わなかった場合、
swappedがfalseであるためbsortにtrueを返してループを抜け、
入れ替えを行った場合はswappedがtrueとなるためbsortにfalseを返し、
ループさせるということなのですね。
大変わかりやすい回答をありがとうございました。
何度も回答いただきまして改めて感謝申し上げます。

補足

すみません、下の御礼コメントを訂正させていただきます。

>swappedがtrueならbsortにfalseを返し、
>falseならtrueを返すということなのですね。
>それで数値の入れ替えを行わなかった場合、
>swappedがfalseであるためbsortにtrueを返してループを抜け、
>入れ替えを行った場合はswappedがtrueとなるためbsortにfalseを返し、
>ループさせるということなのですね。

bsortにtrueあるいはfalseを返すのではなく、
workにtrueあるいはfalseを返し、
もしworkがtrueならreturnでメソッドから抜けるということですね。
失礼いたしました。

回答No.5

notnot

No1,3です。
＞return のあとに何もないのでwhileにnilを返す、つまりtrueではないため

やはりそういう誤解でしたか。No3に書いたとおりなのですが、

whileがループを継続するか終了するかは、while の直後に書かれた式の値を判断に使います。
endの直前の値は無関係です。
while true の場合は、whileループ自体としては、無限ループになります。

なお、while全体の値は、
・ while 直後の値がfalse/nilでループを終了した場合は nil
・ break でループを終了した場合も nil
・ break 式 でループを終了した場合は 式の値
となります。いずれにせよ、end直前の値は無関係です。

補足

再度回答いただきありがとうございます。

>while true の場合は、whileループ自体としては、無限ループになります。
これは理解しておりましたが、while全体の値はreturnの後ろの値ではないのですね。失礼しました。

何度もお聞きして申し訳ないのですが、
return if !swapped　の!はswappedの値を真から偽か、偽から真に変更するだけですよね？
これだと値の入れ替えを行っても行わなくてもreturnでbsortを終了することにはならないのでしょうか？

回答No.4

siffon9

こんにちは

> return のあとに何もないのでwhileにnilを返す、つまりtrueではないため
> ループを抜けるのではないのでしょうか？

returnの実行でif文を終了（＝ whileに戻る）のではありません。
whileのループを飛び越えて、メソッド bsort自体を終了します。

rubyリファレンスをご参照下さい。
http://docs.ruby-lang.org/ja/1.9.3/doc/spec=2fcontrol.html#return

　> 式の値を戻り値としてメソッドの実行を終了します。

お礼

回答ありがとうございます。

>whileのループを飛び越えて、メソッド bsort自体を終了します。

returnはwhileに返すものだと勘違いをしておりました。失礼しました。
bsortにnilを返してメソッドの実行を終了するのですね。

補足

よろしければ、return if !swapped　の!swappedで、
なぜ入れ替えを行わなかった場合、つまりswapped == falseの時のみ、
returnでbsortを終了するのかについても教えていただけますでしょうか。

回答No.3

notnot

No1です。
＞入れ替えがない場合と同様にwhileにnilを返してループを抜けることにはならないのでしょうか？

whileの条件はtrueなので、途中でreturnやbreakで抜けない限りはループし続けます。

「whileにnilを返す」というのが意味不明になってます。

補足

再度回答ありがとうございます。

return if !swappedは
if !swapped
　　return
end
と同じ意味ですよね？
return のあとに何もないのでwhileにnilを返す、つまりtrueではないため
ループを抜けるのではないのでしょうか？

回答No.2

kmee

> 数値の入れ替えがなければ　swapped = false　であるため、
> !swappedはtrueとはならないのでしょうか。

考えが間違っています。
演算子 ! について、よく調べましょう。

お礼

回答ありがとうございます。
下のサイトを見ると、
http://www.rubylife.jp/ini/if/index4.html
!aはaが真の時に偽、偽の時に真を返すとなっているので、
swapped = falseであれば、!swappedはtrueになると考えました。

回答No.1

notnot

＞数値の入れ替えがなければ　swapped = false　であるため、
＞!swappedはtrueとはならないのでしょうか。

それで合ってます。入れ替えが無ければ、swapped = false なので、!swapped==trueとなり、
ループを抜けます。!swappedの ! は、swappedがfalseかnilの時trueになり、それ以外の場合はfalseになる演算子です。

こう書き直した方が良いんじゃ無いかな。
def bsort(data)
　swapped = true
　while swapped
　　swapped = false
　　for i in 0..data.size-2
　　　if data[i] > data[i+1]
　　　　data[i], data[i+1] = data[i+1], data[i]
　　　　swapped = true
　　　end
　　end
　end
end

補足

回答ありがとうございます。

>!swappedの ! は、swappedがfalseかnilの時trueになり、それ以外の場合はfalseになる演算子です。

入れ替えがなければswapped==falseであり、
!swapped==trueとなり、whileにnilを返してループを抜けますよね？
入れ替えがあった場合ではswapped==trueであり、
!swapped==falseとなりますが、
入れ替えがない場合と同様にwhileにnilを返してループを抜けることにはならないのでしょうか？

教えていただいたプログラムのほうがわかりやすいですね。
>data[i], data[i+1] = data[i+1], data[i]
これでdata[i] = data[i+1]　と　data[i+1] = data[i]　を1行で表せるのですね。勉強になります。