バブルソートとセレクションソートの交換回数について

はじめまして。自学でCを学んでいるものです。いきなりですが、タイトルの通り、バブルソートとセレクションソート（直選択ソート）の交換回数が同じになるということは分かるのですが、その理由が分かりません。
何となくわかっているのですが、ｎや数式を用いて論理的に説明しろと言われると、お手上げです。自分の理解のためにもこの点はしっかりと押さえておきたいと思っています。
何卒よろしくお願いします。

No.1 回答者： mtaka2 回答日時： 2009/05/24 10:21

バブルソートと選択ソートでは、交換回数は同じではありません。

選択ソートの方が少なくなります。

バブルソートでは、二重ループの中で必要に応じて交換が行われますので、交換回数はO(n^2)です。

選択ソートでは、二重ループの中は「最小要素の探索」=「比較」のみで、交換はその外の一重ループレベルで行われます。交換回数はO(n)です。

一方、比較回数は、どちらも同じになります。

この回答への補足

回答ありがとうございます。このソートというものは、重複はなしです。

多くのC言語のサイトを見てみると、交換回数が同じとしているのは、また違った条件からなのでしょうか？
転倒数について考えるとその理由が出てくる、という記述のあるサイトがありましたが、それは関係あるでしょうか？

補足日時：2009/05/25 19:34

No.2 回答者： mtaka2 回答日時： 2009/05/26 22:42

入力がある特定の並びについて「バブルソートと選択ソートの交換回数が同じ」であることはありえますが、

総じて見ると「バブルソートと選択ソートの交換回数の比較」では、基本的に「バブルソートの方が交換回数が多い」ことになります。
アルゴリズムの優劣を論じる状況においては「バブルソートと選択ソートの交換回数が同じ」などと言うことはありません。

参考: http://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E% …

> 多くのC言語のサイトを見てみると、交換回数が同じとしている

具体的に、どのサイトにそういう記述があるのか教えてくれませんか?

この回答への補足

必ずそうはならないということは分りました。


http://ew.hitachi-system.co.jp/w/E382BBE383ACE38 …
などです。要素の数が同じであることが条件となっているようです。その場合は交換回数は同じなのでしょうか。

補足日時：2009/05/26 23:00

No.3 ベストアンサー 回答者： mtaka2 回答日時： 2009/05/27 17:22

> 比較回数はバブルソートと同様だが、要素の数が同じなら交換回数は常に同じという、安定性の高いアルゴリズムである。

これは、「バブルソートと選択ソートで交換回数は同じ」という意味ではありません。

「選択ソートでは、要素の数が同じなら、どんな入力データでも交換回数は同じ」という意味です。

たとえば、10要素の選択ソートなら、
「順序的に1番目にくるべき要素を、1番目と交換」
「順序的に2番目にくるべき要素を、2番目と交換」
…
「順序的に9番目にくるべき要素を、9番目と交換」
という流れになり、
どんな入力データであっても、10要素のソートなら交換回数は必ず9回になります。

一方、バブルソートの場合は、入力データの並びによって、交換回数が変わってきます。