古い「Sorting Detective」の宿題 (いくつかのブラック ボックスの並べ替えアルゴリズムが与えられ、それぞれが結果によってどのような例であるかを判断する必要があります) を終えたところです。リスト。全員が課題を提出するまで講師のコードを見ることはできず、クラスで質問をして、問題の解決方法を他の生徒に知らせることもできないため、これは私に残されました。質問があるので、少なくとも 1 週間はこの質問に対する答えを得ることができません。
挿入ソートの教科書の例がソートされたリストでN-1比較を行うのは、現実の世界では常にそうですか、それとも私のインストラクター/教科書のバージョンの挿入ソートの癖ですか?
Google とウィキペディアを検索した後、これに対する答えを見つけることができませんでした。つまり、間違った質問をしている、または彼らがそれを持っていないことを意味します。何か案は？
はい、「教科書」挿入ソートは、入力が既にソートされている場合、N-1 比較を実行します。たとえば、Knuth のThe Art of Computer Programming、Volume 3、§5.2.1、Algorithm S ( Straight insert sort ) を参照してください。各レコード R i (i > 1) について、アルゴリズムは、R i より小さい要素が見つかるまで、要素 R i - 1から R 1までをこの順序で比較します。入力が既にソートされている場合、R i-1は常に R iよりも小さいため、アルゴリズムはレコードごとに 1 つの比較のみを実行します (レコード 1 の比較は実行しません)。
もちろん、代わりにR 1から R i-1までの順序で比較を実行する挿入ソートを作成することもできますが、入力リストが既にソートされている場合は、N*(N-1)/2 回の比較が実行されます。だから、それをしないでください。:)
また、バイナリ検索を使用して、各レコードを挿入する場所を見つけることもできます。これはバイナリ挿入と呼ばれ、Knuth も §5.2.1 で説明しています。繰り返しますが、教科書の直接挿入よりも、既にソートされた入力に対してより多くの比較を実行します (ただし、ランダムな入力ではより少なくなります)。