バブルソートの終了条件

Question

PHPで再帰を使用してバブルソートを実装する場合ですが、
スマートな終了条件はどんな風に書けるでしょうか？

僕の頭に浮んだ終了条件は、最後の要素を順番に各要素と比較していき、一つも入れ替えが無かったら終了、というものでした。
これだとちょっとかっこ悪い気がしまして、
「こっちの方がシンプルでオシャレな終了条件だよ」というものがありましたら、教えて頂けないでしょうか。
よろしくお願い致します。

追記です
要素数は不定とさせて下さい。

Comments

[date]

phpには配列をソートする関数が用意されていますが、実際にバブルソートを組んでやりたいということでしょうか?　

[TomoKubota]

はい、再帰の練習としてやっております。

Answer 1

ソート開始時に要素数を得る手段がないまたはコストがかかるなら、番兵を使うのも一つの方法です。
番兵
仮に一番小さな値が浮かび上がるのであれば、データとして取りうる値よりさらに大きな値を一番上にあらかじめ置いておきます。そしてその値が一つ沈んだ時をもってループを終了し、呼び出し元へ戻ります。すべてのループが終了したときには番兵は一番下に沈んでいるはずなので、それを取り除きます。

しかしそもそもバブルソートがスマートでないので。

Comments

[TomoKubota]

番兵という概念は初めて知りました。とても面白く、参考になりました。
プログラミングの勉強として、スマートでない車輪を何とか「より」スマートに再構築してみようとしておりましたが、大変勉強になりました。
ありがとうございます。

Answer 2

バブルソートで再帰を使うとしたら、終了条件を意図する必要はないはずです。

たぶんこちらのようなことをやろうというのでしょうけれども、これは結局要素の最後から順に決定していくような関数になっています。再帰の呼び出しは要素が先頭決定するまでで、それは

if (s>1)

の部分により、s==0 のときはこの関数は何もせずに抜けるようになっており、結果的に再帰呼び出しが終わるようになっています。

なんですが、再帰で組んだ方が遅いし重いと思いますよ。