No.3ベストアンサー
- 回答日時:
> 比較回数はバブルソートと同様だが、要素の数が同じなら交換回数は常に同じという、安定性の高いアルゴリズムである。
これは、「バブルソートと選択ソートで交換回数は同じ」という意味ではありません。
「選択ソートでは、要素の数が同じなら、どんな入力データでも交換回数は同じ」という意味です。
たとえば、10要素の選択ソートなら、
「順序的に1番目にくるべき要素を、1番目と交換」
「順序的に2番目にくるべき要素を、2番目と交換」
…
「順序的に9番目にくるべき要素を、9番目と交換」
という流れになり、
どんな入力データであっても、10要素のソートなら交換回数は必ず9回になります。
一方、バブルソートの場合は、入力データの並びによって、交換回数が変わってきます。
No.2
- 回答日時:
入力がある特定の並びについて「バブルソートと選択ソートの交換回数が同じ」であることはありえますが、
総じて見ると「バブルソートと選択ソートの交換回数の比較」では、基本的に「バブルソートの方が交換回数が多い」ことになります。
アルゴリズムの優劣を論じる状況においては「バブルソートと選択ソートの交換回数が同じ」などと言うことはありません。
参考: http://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E% …
> 多くのC言語のサイトを見てみると、交換回数が同じとしている
具体的に、どのサイトにそういう記述があるのか教えてくれませんか?
この回答への補足
必ずそうはならないということは分りました。
http://ew.hitachi-system.co.jp/w/E382BBE383ACE38 …
などです。要素の数が同じであることが条件となっているようです。その場合は交換回数は同じなのでしょうか。
No.1
- 回答日時:
バブルソートと選択ソートでは、交換回数は同じではありません。
選択ソートの方が少なくなります。バブルソートでは、二重ループの中で必要に応じて交換が行われますので、交換回数はO(n^2)です。
選択ソートでは、二重ループの中は「最小要素の探索」=「比較」のみで、交換はその外の一重ループレベルで行われます。交換回数はO(n)です。
一方、比較回数は、どちらも同じになります。
この回答への補足
回答ありがとうございます。このソートというものは、重複はなしです。
多くのC言語のサイトを見てみると、交換回数が同じとしているのは、また違った条件からなのでしょうか?
転倒数について考えるとその理由が出てくる、という記述のあるサイトがありましたが、それは関係あるでしょうか?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Excel(エクセル) Excel 効率的な名簿と得点の管理の仕方 8 2022/08/07 08:15
- Excel(エクセル) Excelの50音順ソートを全ての行列に適用するには? 4 2022/12/05 11:28
- Excel(エクセル) エクセルのソート方法について 1 2023/01/13 00:01
- 統計学 加重最小二乗法=①「変数を自然対数変換」=②「誤差項の分散の逆数を重み付け」? 8 2022/11/26 11:15
- 物理学 物理工学系学科-調査課題 2 2022/04/26 18:57
- Excel(エクセル) 結合セルのソートについて 5 2022/04/22 11:57
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- 車検・修理・メンテナンス 国交省「客の要請無き修理をしてはならん!」 あれ?車検時に何でもかんでも修理してるよね? 10 2023/07/28 20:29
- 大学受験 文系の高校2年生です。 進級後(3年生)の科目選択に悩んでいます。 現在は4年制大学へ進学して幼児教 1 2022/10/26 18:04
- 物理学 量子力学 球面調和関数 導出 方位角成分 微分方程式の解 2 2022/07/02 13:40
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
System.IO.Directory.GetFiles...
-
C# DataGridView のヘッダーセ...
-
2次元配列を複数項目でソートし...
-
多次元配列のソート方法
-
VB.NETでファイル名順にファイ...
-
リスト構造のソートで悩んでま...
-
ListViewのソートについて
-
あるディレクトリ内のファイル...
-
ファイル名「1.jpg ~10.jpg~...
-
javaのソートについて。
-
構造体配列のソート
-
線形リストのソートについて
-
VBA基本構文の作り方 2列の...
-
ブック.csvを開かずに他のブッ...
-
プログラミングについて 配列を...
-
jqgrid で 2から3 階層以上の j...
-
構造体配列の並べ替え
-
10個の整数を入力して小さい順...
-
n個の要素で出来る順列組み合...
-
アルゴリズム
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
System.IO.Directory.GetFiles...
-
VB.NETでファイル名順にファイ...
-
ファイル名「1.jpg ~10.jpg~...
-
excel VBA の条件をつけての列...
-
リスト構造のソートで悩んでま...
-
C# DataGridView のヘッダーセ...
-
DataGridViewの複数列を連動し...
-
文字列をソートする方法
-
C# DataTableの行をソートしてD...
-
C言語・要素除去
-
Excelですべての組合せ(重複組...
-
VBA基本構文の作り方 2列の...
-
列のどこをクリックしてもソー...
-
excel VBA リストビューの行...
-
あるディレクトリ内のファイル...
-
コレクションの数値をSortで並...
-
数字文字列のソート方法
-
VBScriptで重複レコードを削除...
-
2次元配列を複数項目でソートし...
-
10個の整数を入力して小さい順...
おすすめ情報