アルゴリズム

質問

この問題も分かりません。

選択整列法は安定か？挿入整列法とバブル整列法はどうか？

よろしくお願いします。

回答No.4

ymmasayan · ベストアンサー

安定な整列法：選択法、挿入法
不安定な整列法：バブル整列法

安定か不安定かは、すでに回答されている通り、同じキーのものが整列後も同じ順番に並んでいるかどうかと言うことです。ご自分で確かめてください。

回答No.3

hitomi13

No.1のahsblueさんの回答は、処理速度について述べられたものだと思いますが、

選択ソート：データ数のみに依存するため、一定。
挿入ソート
　・配列で実装：サーチ法によらず、データの内容に大きく依存。（挿入時のシフトに時間がかかる。逆順列時最大）
　・リストで実装：挿入にかかる時間は一定だが、リニアサーチのみになるため、データの内容に少し依存。（正順列時最大）
バブルソート：データ内容に大きく依存。（並びの交換に時間がかかる。逆順列時最大）
　※ソート完了フラグをつけた場合、正順列ではクイックソートより早い。

です。
参考までに。

回答No.2

punchan_jp

ソーティングで「安定」とは、同じキーをもつ項目の順位がソーティ
ング前後で保たれるかという意味ですね。各ソーティング法のどれ
が安定かは、たいていのアルゴリズムの教科書に書いてあります。
たとえ書いてなくても、アルゴリズムそのものが理解できていれば、
例題を作って試してみることえ、安定かどうかわかります。
（あまり小さい例を作ると、安定でなくてもたまたま安定に見えた
りしますが）

回答No.1

ahsblue

安定の意味が把握しきれませんが・・

選択法　＝　安定
挿入法　＝　安定しない
バブル　＝　安定

だと思います。
理由は、選択ソートの判定回数はバブルソートは全体数にのみ依存し、データ内容には依存しない。
挿入法ではデータ内容に依存するためです。
どうでしょうか？