入力配列を入力として受け取り、並べ替えるプログラムを作成しようとしています。 並べ替えは次のようになります。ランタイムパフォーマンスに基づいて2つのソートアルゴリズムを切り替えるにはどうすればよいですか？
以下のいずれかの並べ替えアルゴリズムを使用して、配列の最初の20％をソートします。プログラムが20％後にソートアルゴリズムが最悪の時間を取っていると識別した場合、プログラムは他のソートアルゴリズムに切り替え、そのソートアルゴリズムを使用して配列をソートし続けます。 私がここで直面している問題は、ソートアルゴリズムが最悪の時間を取っているかどうかを知る方法です。私が使うことになる
ソートALGOSは以下のとおりです。
クイックソート、マージソート 、 バケットソートヘルプの任意の種類は本当に感謝されるだろう
。
「配列の最初の20％をソートする」とはどういう意味ですか？
配列のソートされたバージョンが最初に必要なことを意味しているので、配列の並べ替えの程度を確認することができます。次にソートされたバージョンを最初に配列をソートすることなく思いついていますか？それは鶏と卵の問題のようなものです。
主な質問に戻って、私が覚えている限り、ほとんどのソートアルゴリズムは、コピー操作の回数に基づいてランタイムの複雑さを分析しています。たとえば、要素を適切な場所に挿入する必要がある場合は、要素を移動する必要があるため、挿入ソートには多くのコピー操作が必要です。他のアルゴリズムは、スワップ操作の数に基づいて分析され、3回のコピー操作に分解することもできます。
しかし、上で述べたように、配列をx％ソートとして定義する方法はわかりませんが、ソートされた配列を最初に持たないソートレベルをどのように測定できるかはわかりません。
配列の最初の20％をソートする方法は...長さが100の配列です。最初にアルゴをランダムにソートし、アルゴの最初の20要素をソートしてから、アルゴのパフォーマンスを特定する必要がありますそれが最悪の場合の実行時間を与えていない場合、私はソートを続けるか、そうでなければ私はいくつかの他のalgoに切り替えるでしょう。しかし、事は、どのようにalgoが最悪の場合を与えているかどうかを知ることができます。 –
ヒープソートの最悪の場合、時間の複雑さnlognと一定のスペースを使用します。
まず、クイックソートが配列の優先アルゴリズムですが、主にmergesortがO（N）の追加メモリを必要とするため、マージがリストに優先されます。
問題の解決方法の1つは、クイックソートを最初に実行した後に、各分割を行う前に、配列のどの部分にいくつの要素があるかをまず確認することです。その数値が比較的小さい場合は、bucketsortを実行し、そうでない場合はquicksortを続行します。
しきい値を見つけるには、長さと分布の異なるランダムな配列の大きなテストセットを作成し、クイックソートとバケットソートのパフォーマンスを比較します。テストアレイを作成するときは、できるだけ使用シナリオをシミュレートしようとします。そのようにして、ある程度の誤差があれば、配列内のさまざまな要素の数のしきい値が決まります。
ほとんどの場合、しきい値〜1000の要素を使用しましたが、これは使用シナリオに非常に依存するため、テストの実行が最適です。
提案していただきありがとうございます。私はランダムに最初のアルゴリズムを選ぶことを計画しています。そしてalgoが配列の最初の20％をソートすると、私は時間の複雑さと実行時間も持ちます。私は時間の複雑さを実際の実行時間と比較して他のアルゴリズムに切り替えることができないので、今ここで立ち往生しています。 –
"introsort"を参照してください。 –
バケットソートの場合、バケット全体の要素の分布を探すことができます。クイックソートの場合、分割ステップ後にピボットの位置を見ることができます。マージソートは平均複雑度と同じ最悪ケースの複雑さを持つため、このハイブリッドアプローチの最初のアルゴリズムとしてはあまり適していません。 – NPE
逆数の数を数えると、* 1回のみの直線パスがかかります。 – joop