選択ソートがバブルソートよりも速いのはなぜですか？

提供したすべての複雑さは真実ですが、与えられています Big O表記であるため、すべての加算値と定数が省略されます。

質問に答えるには、 dこれら2つのアルゴリズムの詳細な分析に焦点を当てます。この分析は手作業で行うことも、多くの本で見つけることもできます。 クヌースのコンピュータプログラミングの芸術の結果を使用します。

比較の平均数：

• バブルソート：$ \ frac {1} {2}（N ^ 2-N \ ln N-（\ gamma + \ ln2 -1）N）+ \ mathcal O（\ sqrt N）$
• 挿入ソート：$ \ frac {1} {4}（N ^ 2-N）+ N-H_N $
• 選択ソート：$（N + 1）H_N-2N $

これらの関数をプロットすると、次のようになります。

ご覧のとおり、両方の並べ替え方法が同じ漸近的であっても、要素の数が増えると、バブルソートははるかに悪化します。複雑さ。

この分析は、入力がランダムであるという仮定に基づいています。これは常に当てはまるとは限りません。ただし、並べ替えを開始する前に、入力シーケンスをランダムに並べ替えて（任意の方法を使用して）平均ケースを取得できます。

実装に依存するため、時間計算量分析を省略しましたが、同様の方法を使用できます。

コメント

• "に問題があります。入力シーケンスをランダムに並べ替えて平均ケースを取得できます"。ソートに必要な時間よりも速く実行できるのはなぜですか？
• $ N $がシーケンスの長さである場合、$ N $の時間がかかる任意の数値のシーケンスを並べ替えることができます。 '比較ベースの並べ替えアルゴリズムには、少なくとも$ \ mathcal O（N \ log N）$の複雑さが必要であるため、$ N $を追加しても'の複雑さは'それほど変更されません。とにかく、時間ではなく比較について話しているのですが、時間の複雑さは、回答で述べたように、実装と実行中のマシンによって異なります。
• 私は眠かったと思います、そうです、シーケンスは線形時間で並べ替えることができます。
• $ H_N = \ Theta（log N）$なので、比較境界は選択ソートに対して正しいですか？ 'は、平均してO（n log n）の比較を行うことを意味しているようです。
• ガンマ= 0.577216はオイラーの定数です'の定数。関連する章は、"プログラミングの芸術" vol3セクション5.2.2pgです。 109と129。バブルソートのケース、特にO（sqrt（N））項をどのようにプロットしましたか？無視しましたか？

漸近コスト、または$ \ mathcal O $表記、関数の引数が無限大になる傾向があるため、関数の制限動作、つまりその成長率について説明します。

関数自体。例：比較やスワップの数は、同じ漸近コストの2つのアルゴリズムで異なる場合があります。ただし、それらが同じ速度で成長する場合に限ります。

より具体的には、バブルソートには平均で$ n / 4が必要です。エントリごとの$スワップ（各エントリは初期位置から最終位置に要素ごとに移動され、各スワップには2つのエントリが含まれます）、選択ソートには$ 1 $のみが必要です（最小/最大が見つかると、1回スワップされます）配列の最後まで）。

比較の数に関して、バブルソートには$ k \ times n $の比較が必要です。ここで、$ k $はエントリの初期位置とエントリの間の最大距離です。その最終的な位置は、通常、均一に分散された初期値の場合は$ n / 2 $より大きくなります。ただし、選択ソートでは、常に$（n-1）\ times（n-2）/ 2 $の比較が必要です。

要約すると、漸近限界は、入力サイズに対してアルゴリズムのコストがどのように増加するかをよく理解できますが、同じセット内の異なるアルゴリズムの相対的なパフォーマンスについては何も述べていません。

コメント

• これは非常に良い答えです
• どの本が好きですか？
• @GrijeshChauhan：本は好みの問題なので、一粒の塩でどんな推薦もしてください。個人的には、Cormen、Leiserson、Rivest 'の"アルゴリズムの概要"が好きです。これは、いくつかのトピックの概要を示しており、Knuth ' s "アートオブコンピュータープログラミング"特定のトピックに関する詳細/すべての詳細が必要な場合はシリーズ。本の質問が以前にここで尋ねられたかどうかを確認するか、' tがない場合はその質問を投稿することをお勧めします。
• 私にとって、3番目のパラグラフあなたの答えは実際の答えです。他の回答で示されている、大きな入力のグラフではありません。

バブルソートはより多くのスワップ時間を使用しますが、選択ソートはこれを回避します。

並べ替えを選択すると、最大でn回スワップされます。ただし、バブルソートを使用すると、ほぼn*(n-1)がスワップされます。そして明らかに、メモリ内であっても、読み取り時間は書き込み時間よりも短くなります。比較時間やその他の実行時間は無視できます。したがって、スワップ時間は問題の重大なボトルネックです。

コメント

• Bartekによる他の回答の方が合理的だと思いますが、'投票できませんまたはコメント…ところで、私はまだ執筆時間の影響が大きいと思います。彼がこれを見て同意すれば、これを考慮に入れてくれることを願っています。
• 時間のあるユースケースがあるため、比較の数を単純に無視することはできません。 2つのアイテムを比較するために費やされる時間は、2つのアイテムを交換するために費やされる時間をはるかに超える可能性があります。非常に長い文字列（たとえば、それぞれ10万文字）のリンクリストについて考えてみます。各文字列の読み取りは、ポインタの再割り当てを行うよりもはるかに時間がかかります。
• @IrvinLimあなたは正しいと思いますが、気が変わる前に統計データを確認する必要があるかもしれません。