ここから本文です

ソートアルゴリズムの計算量についてです。

アバター

ID非公開さん

2019/7/2010:08:36

ソートアルゴリズムの計算量についてです。

例えば選択ソートの場合はソートしたい順の逆順になっている場合に計算量最悪になると思いますが、
挿入ソートの計算量最悪O(n^2)になる場合の元データの並び順はどのようなものになりますか?

閲覧数:
10
回答数:
1

違反報告

ベストアンサーに選ばれた回答

bul********さん

2019/7/2213:25:21

挿入ソートの最悪ケースは逆順に並んでいる場合です。挿入ソートは要素を適切な位置に挿入するために、挿入位置以降にある要素をずらす必要がありますが、逆順に並んでいるとそれが毎回最大量必要となります。
最良ケースはもちろんすでにソート済みの場合です。データ数を N とすると、ソート済みの場合は比較回数は N-1 回、交換回数は 0 回です。

余談ですが、交換ソートは実際にプログラムを実行してみるとわかりますが、データの並びによって処理時間はそんなに変わりません。比較回数は常に N×(N-1)÷2 になり、交換回数は最大でも N-1 回です。
インデックスを保存する必要がありますが、大きなデータ(構造体)ソートする場合は、データそのものを移動する必要のある挿入ソートに比べ、交換回数の少ない交換ソートが有利になります。

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる