Serviceを読んで理解し、同意したものとみなします。スタック・オーバーフローはプログラマーとプログラミングに熱心な人のためのQ&Aサイトです。するというもの(iとjが共に前から後ろへ。i}というもの(iは前から、jは後ろから)があるように見受けられます。当方の環境で実験したところ、1000万要素などになると露骨にp1の方が遅くなります(比較回数は少なめだが交換回数が多い)。これは前者のpartition()が間違って書かれているのでしょうか。複数のサイトで誤りが放置されているとは考えにくいので実際は私に何か勘違いがあるのだと思います。ご指摘いただければ幸いです。最適化-O2を使っても同様。1.73GHz!)を引っぱり出して実験したが同様。Expressが入っていたので試したが同様。シャッフルしたユニークな配列の場合、定数倍っぽい差の出方に改善した(最適化-O2を使うとさらに差は縮まる)。いう結果になりました。メモリ(RSS)は3.7G程度を使用しています。以下になってしまいます。発生する場合がありました)。mingwだと顕著に差が出ました。14:401randomize()の実装をstd::mt19937にするとMinGWでも速度差出ませんし、randomize()の実装をMSVC互換の線形合同法の上位ビットにするとCygwinでも速度差出るので、qsortで計算量の増えるパターンになっているのかもしれません。N)ではなくO(N^2)のワーストケースになります。VCやMinGWではRAND_MAXが0x7fffしかないため10000000要素の配列では305個程度同じ値があり、性能の劣化が起こります。0);}とすると他の方の回答にあるLinux環境でも再現するはずです。N)で処理できますが、partition()はlowかhighに近いインデックスで分割し1:N-1の分割しかできません。結果としてquickSort()はO(N^2)に近くなってしまいます。ソートする場合、p1ではピボット値以外の要素以外はピボット値以上側に割り振られ21回比較が発生します。比較1回p2では両端から挟み込むので、ピボット位置が中央にきて比較16回で済みます。0]のような入力に対してはp1もp2もうまくいかないので実用上はさらに工夫が必要されていることが多いようです。個の銅バッジ乱数の範囲を0...0x7FFFにすることにより、こちらでも「上」「下」の顕著な性能差を観測することができました。した解析は出来ていませんが、QuickSortのワーストケースに近い振る舞いをしやすくなるのだろうと言うのは納得です。「下」のアルゴリズムはそのような影響を受け難いのかについて何らかの知見をいただけるとさらに良い回答になるかと思います。22:032実例を追記しました。ソート済み入力も考えるとさらに難しいですね。|4当方の環境では要素数を1億にしても速度差はせいぜい10%前後でした。「下」の方が有意に早かったのですが、交換が発生する回数をカウントするためのコードを付け加えた場合など、「下」の方が遅くなることもありました。使用する言語やCPU、要素数や要素の分布によっても、結果は変動するだろうと思います。「上」の方では、配列全体を舐めて、pivotより小さな数に対して必ず交換が発生するのに対して、「下」の方では配列を前と後ろから舐めて、pivotより大きな数が前側/pivotより小さな数が後ろ側にあるときだけ交換が発生しします。後者がN/4程度(前半に入る要素数の平均して2つに1つは交換が必要)の期待値で交換が発生することになります。(実際には平均してももうちょっと大きな違いが発生しましたが。)その代わり比較や条件分岐の数が少ない訳ですから、交換のコストより比較や条件分岐のコストが相対的に高いなら「上」が有利、交換のコストの方が高いなら「下」が有利と言えるかと思います。これは前者のpartition()が間違って書かれているのでしょうか。「上」の方のアルゴリズムを試してみて、なにか間違った答えが出たことがあるでしょうか。n)の計算量でソーティングが完了することには変わりはありません。ご自分の環境に応じて、より良い特性を示す方のアルゴルズムを採用されれば良いことだろうと思います。追記zakkiさんの追記された部分まで読めばほぼ解決かと思うのですが、私の場合何度も考え直さないとわからなかったので、もしかして中にはご理解が深まる方もおられるかもしれないと言うことで、一応考えたことを整理しておきます。実はp1(「上」)とp2(「下」)との間には分割後の状態に若干の差異があります。|(pvがピボット値。pivotに等号をつけて<=にするとちょっと様子が変わるのですが、簡単のためそちらは省略。|p1の分割後は、pvと同位の要素は必ずpiよりもhi側に固まるのに対して、p2ではpvと同位の要素がpiよりlo側にもhi側にも現れることになります。(p2でもp1と同じように、pvと同位の要素がhi側に固まる可能性も無いでは無いが、極めてまれ。|と言う分割になり、たとえpvに最小値を選んでしまった場合でも(pvと同位の要素が多数あるならば)、QuickSort的に最悪の分割になることは滅多に起こらないわけです。部分配列の要素が全部同じ値になるまで分割が進むと(1億要素に対し0...0x7FFFの乱数を割り当てると同じ値の要素が3000件ほどあると期待される)、p1では常に最悪分割になるのに対し、p2では常にほぼ中央の最善分割になると言うのはzakkiさんの実例でよくわかるだろうと思います。言うわけで、同位の値が発生するなんてことは実際のソーティングではよくあることなのに、考えが至らなかったのはお恥ずかしい限りです。問題点を把握して、実例を交えて解説していただいた、zakkiさんには改めて感謝いたします。(upvoteが1回しか出来ないのが残念です。個の銅バッジ当方での試行結果を追記しました。化石CPUでアレですが「ここまで差がつくだろうか?」というのを疑問に思い今回質問した次第です。「私の環境でswapのコストが高いことに起因している。実装自体は両者とも正しい。さん、大丈夫ではないような差がついていますね。g++での「上」アルゴリズムのコーディングに間違いがある可能性もありそうです。(私は最初「上」アルゴリズムのコードを間違えてしまい、随分悩んでしまいました。4.2最適化あり1億件ランダムInt(64bit)で、上が9.8秒、下が8.7秒くらいです。g++のコードを示していただければ、修正すべき点を見つけられるかもしれません。さん、コードのご提示ありがとうございます。長いコードでもないので、本文中に直接記入していただいた方が良いように思います。将来リンク切れの心配もなくなりますし。ご提示のコード、範囲外アクセスになる可能性があったので、一箇所だけ書き換えさせていただきました。j--;元のままだとjがlowより小さい値になってしまい、時には0より小さくなる可能性もあります。(そう言う意味では「下」アルゴリズムは若干不完全。時にはquick2の方が時間がかかる時もあり、私のSwiftコードよりもっと差が少ないと言う結果になりました。「300経っても終わらず」の時からコードを全く修正していないのであれば、そちらの実行環境に何らかの原因がありそうです。16.04を入れたマシンが2GBだったので試してみました。N3050@1.6GHz,-O2)、やはりそれほど顕著な差は出ないですね。i7マシンとほぼクロック数比例の違いしか出なかった感じです。Sortは1960年にアントニー・ホーアさんが発表したものです。321に掲載されています。toが多用されるなど細部は異なりますが、p2に近い実装になっていました。p1の出典は分かりませんが、スワップコスト(intでなく大きな構造体など)や配列サイズ(大規模配列でなく任意のサイズで良好な性能が得られるなど)も踏まえて改良されたものではないでしょうか。実装されていても要件に合致します。実装しているようです(ってかホントは逆で、イントロソートの有用性が広く知られたので「平均して」を取ることにしたらしい)イントロソートは途中までクイックソート、再帰が深くなったらヒープソートに切り替える(と、クイックソートの最悪状況を避けられる)というアルゴリズムです。実装を見てみたところ、イントロソートで「ほぼソート」し、挿入ソートするという方法を取っていました。挿入ソートは「ほぼソート」済み状態のデータに対してきわめて高速であることが知られています。値のほうが早く終了しました。|回答スタック・オーバーフローに参加してくれて、ありがとうございます!質問の回答を共有してください。回答を説明し、自分の検討結果も共有してください。意見を述べること(意見を述べるなら、参照リソース、自分の経験で意見をサポートしてください)さらにサポートが必要な場合このヘルプを参考してください。“回答を投稿”をクリックすることで利用規約、プライバシーポリシー、及びクッキーポリシーに同意したものとみなされます。タグが付いた他の質問を参照するか、自分で質問をする。質問のフィードこのRSSフィードを購読するには、このURLをコピーしてRSSリーダーに貼り付けてください。