ソートアルゴリズム（選択法とバブルソート）の交換回数

バブルソートと選択法について、交換回数がわかりません。
比較回数については、ネットで検索したり、本に載っているので分かりやすいのですが、交換回数があまり載っていなく…。

選択法の交換回数の最大値は、n-1でしょうか？
バブルソートの交換回数の最大値は、nでしょうか？

交換回数については、選択法のほうがバブルソートより少なくてすむそうですが、上の答えでいいのかわかりません。

どなたか教えてください。お願いしますm(_ _)m

No.1 回答者： BLUEPIXY 回答日時： 2006/04/19 00:18

アルゴリズムで違うような気がしますが、

選択法というのが、未決定のｎ個のリストから最小値を決定し、その最小値の位置のデータと交換するというようなアルゴリズムであるなら、
最悪の場合、それぞれのデータを交換する必要がありますが、最後の１コは、必然的に位置が決まるので交換しないので、
選択法の場合：n-1 回

バブルソートを隣接するデータを大小関係で交換するアルゴリズムだとすると、
最悪の場合、
最初の１つのデータが決まるのにｎ－１回の交換が必要で
次のデータが決まるのにｎ－２回の交換が必要で
…
最後のデータが決まるのに１回の交換が必要なので
ｋ＝１～ｎ－１Σｋ
バブルソートの場合：ｎ（ｎ－１）／２回
になると思います。

この回答へのお礼

ありがとうございました！！

お礼が遅くなりましてすみませんでした。


交換回数を知りたかったのでとても助かりました。m(_ _)m

お礼日時：2006/05/03 08:01