あなたが与えられた場合：
どのソートアルゴリズムを選択しますか? 挿入とクイックソートの間で議論しています。挿入ソートの最良のケースは O(n) ですが、最悪のケースは O(n 2 ) であることはわかっています。また、メモリが限られているという事実を考慮して、データを2つの部分に分割し、それぞれでクイックソートを実行してから、すべてをマージします. データを分割するのに O(n) 時間、データをマージするのに O(n) 時間、クイックソートを使用してデータを並べ替えるのに O(n log n) 時間がかかり、正味実行時間は O(n log n) です。
これを改善する方法について何か提案はありますか？
あなたのマージソートのようなアプローチは非常に合理的です。より一般的には、このタイプのソート アルゴリズムは外部ソート アルゴリズムと呼ばれます。これらのアルゴリズムは、多くの場合、説明したとおりに機能します。データのサブセットをメモリにロードし、並べ替えてから、ディスクに書き戻します。最後に、マージ アルゴリズムを使用してすべてをマージします。ロードする量と使用するソート アルゴリズムの選択は、通常、主要な関心事です。主にソート アルゴリズムの選択に焦点を当てます。
クイックソートの最悪の場合の動作に関する懸念は、一般的に心配する必要はありません。ピボットをランダムに選択すると、実行時間が本当に悪い可能性が低くなるからです。ランダム ピボット戦略は、最悪の場合の入力がないため、データが既に並べ替えられている場合でもうまく機能します (誰かが乱数ジェネレーターとシードを知っている場合を除きます)。この最悪のケースを回避するために、最悪のケースの動作を持たないintrosortのようなクイックソート バリアントをソート アルゴリズムとして使用することもできます。
とはいえ、データがすでに部分的に並べ替えられていることがわかっているので、並べ替え手順の適応並べ替えアルゴリズムを調べることができます。これについて挿入ソートについて言及しましたが、はるかに優れた適応アルゴリズムが世の中にあります。メモリが不足している場合 (説明したように)、最適なランタイムO(n)、最悪のランタイム O(n log n) を持ち、O( 1) メモリ。他のアルゴリズム (Python のtimsort、natural mergesort、または Cartesian tree sortなど) ほど適応的ではありませんが、メモリ使用量は少なくなります。また、優れたクイックソートほど高速ではありませんが、データの大部分が実際にソートされている場合は、かなりうまく機能します。
お役に立てれば！
一見すると、私はクイックソートで分割して征服し、それを 1 日と呼んでいます。多くのアルゴリズムの問題は考えすぎです。
ここで、使用するテスト データがあり、それを本当に把握したい場合は、抽象クラスを真ん中に置いてベンチマークします。私たちは一日中物事を片付けることができますが、データがすでに部分的にソートされていることを知っているので、テストする必要があります. ソートされたデータは、ほとんどのクイックソートの実装で最悪のパフォーマンスをもたらします。
多くの並べ替えアルゴリズムがあり、一部は並べ替えられたセットに適していることを考慮してください。また、セットがソートされていることがわかっている場合は、n 回で別のセットとマージできます。したがって、並べ替えられたデータのチャンクを最初に特定すると、単一 (n) パスを追加することと、クイックソートが (n 2 ) 時間かかる可能性を大幅に減らすことを比較すると、多くの時間を節約できます。