問題タブ [introsort]

イントロソートはクイックソートで始まり、再帰の深さがソートされる要素の数に基づくレベルを超えると、ヒープソートに切り替わります。その数は何ですか？特定の範囲または制限値はありますか?

クイックソート、ヒープソートを使用してイントロソートを実装しました。私の手書きバージョンは、パラメーターとして渡されたヒープソートに切り替えるための再帰の深さ、中央値3のピボット選択を使用したD.Musserの提案に基づいています。単純挿入ソートに切り替えるための要素のしきい値は16でした。

C++ は組み込みの std::sort にイントロソート (イントロスペクティブ ソート) を使用し、クイックソートで開始し、深さの制限に達するとヒープソートに切り替えることを読みました。

また、深さの制限は 2*log(2,N) であると想定されていることも読みました。

この値は純粋に実験的なものですか? それとも、その背後にいくつかの数学的理論がありますか?

イントロソートについて読んでいました。私はそのほとんどを理解していますが、ほとんどの実装がそのクイックソート部分に対して1つの再帰を持つ傾向がある理由を理解できません。クイック ソートの標準実装では、クイック ソートに 2 つの再帰を使用します。

ここで、同じものを次のように変更してみました。

私は 2 つの変更を行いました。

私の変更の有無にかかわらず、プログラムは正常に動作するようです。しかし、オンラインのほとんどの実装で単一再帰を使用する理由を知りたかったのです。

現在、並べ替えアルゴリズムを研究しており、HeapSort と Introspective Sort を実装する必要があります。

私は HeapSort を正常に実装したと思います (コードは機能し、ランダムなサイズの何百万ものランダム配列で試し、常に機能しました)、ここに私のコードがあります:

moveDown コードは次のとおりです。

これらの 2 つの方法は完全に正常に動作するはずです。何度もテストしましたが、問題は発生しませんでした。

また、これらの 2 つの方法から始めて、内省的並べ替えを実装しようとしています。私のコードは次のようなものです。

メソッド isort と hsortAux が正常に機能すると仮定すると、上記のコードも問題ないと思います。私のテストでは、ヒープソートが呼び出されたときにのみ失敗することに気付きました。tukey 近似を使用してピボット インデックスを決定する場合と、たとえば常に配列の最初の要素のようなランダム ピボットを選択する場合の両方で、コードは機能するはずです (ターゲットはそれを機能させることです)。私は多くのクイックソートの実装を試しましたが、それらはすべて機能し、すでに述べたように、コードはヒープソートが呼び出されていないときに機能するため、クイックソートを使用したパーティショニングは正しいはずです。パーティショニングは、実際には完全に機能する別の方法でのクイックソートからのコピーペーストです。

メソッド isort と tukeyApproximation が意図したとおりに機能することは確かです。なぜなら、それらを単独でクイックソートの実装でテストし、問題なく機能するからです。

ただし、最小値と最大値の間の配列部分でのみ機能するヒープソート (hsortAux と呼ばれるメソッド) を実装することはできないようです。こことGoogleで答えを探すのに数時間費やしました。他の人のコードを見て自分のバージョンを実装しようとしましたが、何度も失敗し、ここであなたの時間を無駄にしています:)。機能する heapSort をなんとか作成できましたが、チューキー近似によってピボットが選択されなかった場合 (たとえば、配列の最初の要素またはその部分のランダムな要素) は機能しないようでした。

元のhsortAuxから派生した現在のhsortAuxコードは次のとおりです。

moveDownAux は、配列部分でのみ機能する moveDown メソッドであるはずですが、実装方法がまったくわかりません。代わりに以前の moveDown メソッドを使用しようとしましたが、明らかにまったく機能しません。moveDownAux を実装するとき、minという変数が必要かどうかさえわかりません。

これが私の現在の moveDownAux メソッドです:

お時間とご回答ありがとうございます。

ちょっとした楽しみとして、私は Introsort の反復バリアントを実装しようとしています。デフォルトの実装は次のようになります。

たまたま反復クイックソートを実装しているため、反復イントロソートの基礎としてのglibc実装を使用しています。qsortqsort

私の実装は次のようになります。

10ランダムな要素へのサイズの入力では100'000問題なく動作するように見えますが、100 万の要素をテストすると、突然数秒まで遅くなり、100 万の要素を持つ単一の配列には長すぎます。

これを修正するにはどうすればよいですか?