52450


([QuickSort:GeeksforGeeks](https://www.geeksforgeeks.org/quick-sort/)を参照)

QuickSortの大枠を、

[code]

    /* low  --> Starting index,  high  --> Ending index */
    quickSort(arr[], low, high) {
        if (low < high) {
            pi = partition(arr, low, high)
    
            quickSort(arr, low, pi - 1)
            quickSort(arr, pi + 1, high)
        }
    }
    
[/code]

としたとき、partition()には、先述GeeksforGeeksのような

[code]

    /* 以下 p1 と表記 */
    partition (arr[], low, high) {
        pivot = arr[high]
    
        i = low - 1
    
        for (j = low; j <= high - 1; j++) {
            if (arr[j] <= pivot) { // ***
                i++
                swap arr[i] and arr[j]
            }
        }
        swap arr[i + 1] and arr[high]
        return (i + 1)
    }
    
    // GeeksforGeeks からまるまる引用
    // この *** 部分の比較を < に変更したものを p1' とする
    
[/code]

というもの（iとjが共に前から後ろへ。[VisuAlgo](https://visualgo.net/ja/sorting)他いくつかのサイトで見かける）と、

[code]

    /* 以下 p2 と表記 */
    partition (arr[], low, high) 
    { 
        pivot = arr[high]
    
        i = low
        j = high - 1
    
        for ( ; ; ) {
            while (arr[i] < pivot) i++
            while (i < j && pivot < arr[j]) j--
            if (i >= j) break
            swap arr[i] and arr[j]
            i++
            j--
        }
        swap arr[i] and arr[high]
        return i
    }
    
[/code]

というもの（iは前から、jは後ろから）があるように見受けられます。

当方の環境で実験したところ、1000万要素などになると露骨にp1の方が遅くなります（比較回数は少なめだが交換回数が多い）。  
これは前者のpartition()が間違って書かれているのでしょうか。  
複数のサイトで誤りが放置されているとは考えにくいので実際は私に何か勘違いがあるのだと思います。ご指摘いただければ幸いです。

* * *

実験

(Core2Duo E4600, g++ 8.2.0 最適化なし, vector<int>, 乱数, メモリは全2GBで余力は0.8GB程度)

[code]

    |     | 10^6 個 | 10^7 | 10^8  |
    +-----+-------- +------+-------+
    | p1' | 0.6 秒  | 14.6 | 953.3 |
    | p2  | 0.4     |  4.5 |  51.1 |
    
    なお p1 そのままを使うとさらに遅くなる
    | p1  | 1.0     | 52.9 | 未計測|
    
[/code]

[使ったC++コード](https://ideone.com/ixuBOs)

  * 常駐ソフト等が悪さをしているのかと思いセーフモード起動で試したが同様
  * 最適化-O2を使っても同様。108件で208秒vs12秒
  * さらに化石PC(PentiumM 1.73GHz!)を引っぱり出して実験したが同様。107件で21秒vs6秒
  * コンパイラの違いかと思いVisual C++ 2010 Expressが入っていたので試したが同様。108件で270秒vs12秒
  * partition()呼び出し回数・swap回数をカウントしたところ異常な伸び方はしていない

[code]

    |     |        10^6 個          |   10^7    |   10^8    |
    +-----+-------------------------+-----------+-----------+
    | p1' | 0.01億calls, 0.1億swaps | 0.1 , 1.1 | 1.0, 12.0 |
    | p2  | 0.006      , 0.05       | 0.06, 0.7 | 0.6,  8.6 |
    
[/code]

* * *

実験2: ソート対象の要素の重複具合について

[0..ARRAY_SIZE) をシャッフルしたユニークな配列の場合、定数倍っぽい差の出方に改善した（最適化-O2を使うとさらに差は縮まる）。

[code]

    |     |10^6 |10^7 | 10^8 |
    +-----+-----+-----+------+
    | p1' | 0.6 | 6.8 | 79.6 |
    | p2  | 0.4 | 4.5 | 51.5 |
    
[/code]

[0..ARRAY_SIZE) の先頭何%かを同一要素にしてからシャッフルした配列の場合、重複を多くしていくとp1'の性能が劣化した

[code]

    10^7 件 において
    
    |     | 0.1%| 0.4% | 0.5%
    +-----+-----+------+------
    | p1' | 7.4 | 11.6 | クラッシュ(スタック溢れ？)
    | p2  | 4.5 |  4.5 | 4.5
    
[/code]

[使ったコード断片](https://ideone.com/eKTw0z)

* * *

解決事項

  * 複数人による検証によるとアルゴリズム、コードに致命的誤りはない (聞きたかったことは解決)
  * p1 は同一要素含みの配列に弱い


CC BY-SA 4.0
2019-01-26T01:37:41.287
52329
2019-02-01T14:46:22.747
2019-02-01T14:46:22.747
31930
31930
question
アルゴリズム
クイックソートの2種類の実装法で実行速度に顕著な違いが出る


当方の環境では要素数を1億にしても速度差はせいぜい10%前後でした。「下」の方が有意に早かったのですが、交換が発生する回数をカウントするためのコードを付け加えた場合など、「下」の方が遅くなることもありました。使用する言語やCPU、要素数や要素の分布によっても、結果は変動するだろうと思います。

「上」の方では、配列全体を舐めて、pivotより小さな数に対して必ず交換が発生するのに対して、「下」の方では配列を前と後ろから舐めて、pivotより大きな数が前側/pivotより小さな数が後ろ側にあるときだけ交換が発生しします。

pivotがうまく中央値になったとして(常に「最後の要素」では、そううまくいきませんが)、分割したい部分配列のサイズをNとすると、前者がN/2(前半に入る要素数そのまま),
後者がN/4程度(前半に入る要素数の平均して2つに1つは交換が必要)の期待値で交換が発生することになります。(実際には平均してももうちょっと大きな違いが発生しましたが。)

その代わり比較や条件分岐の数が少ない訳ですから、交換のコストより比較や条件分岐のコストが相対的に高いなら「上」が有利、交換のコストの方が高いなら「下」が有利と言えるかと思います。

**_これは前者のpartition()が間違って書かれているのでしょうか。_**

「上」の方のアルゴリズムを試してみて、なにか間違った答えが出たことがあるでしょうか。平均して`O(n*log
n)`の計算量でソーティングが完了することには変わりはありません。ご自分の環境に応じて、より良い特性を示す方のアルゴルズムを採用されれば良いことだろうと思います。

* * *

**追記**  
zakkiさんの追記された部分まで読めばほぼ解決かと思うのですが、私の場合何度も考え直さないとわからなかったので、もしかして中にはご理解が深まる方もおられるかもしれないと言うことで、一応考えたことを整理しておきます。

実はp1(「上」)とp2(「下」)との間には分割後の状態に若干の差異があります。

p1

[code]

     lo             pi                   hi
    |    <pv       |pv|        ≧pv         |
    
[/code]

(pvがピボット値。p1の交換条件の`arr[j] < pivot`に等号をつけて`<=`にするとちょっと様子が変わるのですが、簡単のためそちらは省略。)

p2

[code]

     lo                 pi               hi
    |      ≦pv         |pv|     ≧pv        |
    
[/code]

p1の分割後は、pvと同位の要素は必ずpiよりもhi側に固まるのに対して、p2ではpvと同位の要素がpiよりlo側にもhi側にも現れることになります。(p2でもp1と同じように、pvと同位の要素がhi側に固まる可能性も無いでは無いが、極めてまれ。)

これはpvとして最小値を選んでしまった場合にはさらに顕著で、

p1

[code]

     pi
    (lo)                                 hi
    |pv|               ≧pv                 |
    
[/code]

p1の方では必ずQuickSort的に最悪の分割となるのに対して、p2の方は、

p2

[code]

     lo      pi                          hi
    |  =pv  |pv|           ≧pv             |
    
[/code]

と言う分割になり、たとえpvに最小値を選んでしまった場合でも(pvと同位の要素が多数あるならば)、QuickSort的に最悪の分割になることは滅多に起こらないわけです。

部分配列の要素が全部同じ値になるまで分割が進むと(1億要素に対し0...0x7FFFの乱数を割り当てると同じ値の要素が3000件ほどあると期待される)、p1では常に最悪分割になるのに対し、p2では常にほぼ中央の最善分割になると言うのはzakkiさんの実例でよくわかるだろうと思います。

* * *

と言うわけで、同位の値が発生するなんてことは実際のソーティングではよくあることなのに、考えが至らなかったのはお恥ずかしい限りです。しっかりと問題点を把握して、実例を交えて解説していただいた、zakkiさんには改めて感謝いたします。(upvoteが1回しか出来ないのが残念です。)


CC BY-SA 4.0
2019-01-26T04:52:23.913
52335
2019-02-01T13:27:24.263
2019-02-01T13:27:24.263
13972
13972
52329
answer


クイックソートでは(ほぼ)ソート済みの配列や同一要素の配列に対して平均的なO(N log N)ではなくO(N^2)のワーストケースになります。  
VCやMinGWでは`RAND_MAX`が0x7fffしかないため10000000要素の配列では305個程度同じ値があり、性能の劣化が起こります。

[code]

    void randomize(vector<int> &arr) {
      std::mt19937 mt(0);
      uniform_int_distribution<int> dist(0, 32768);
        for(int i = 0; i < ARRAY_SIZE; ++i) {
          arr[i] = dist(mt);
        }
    }
    
[/code]

やさらに極端に

[code]

    void randomize(vector<int> &arr) {
      fill_n(arr.begin(), ARRAY_SIZE, 0);
    }
    
[/code]

とすると他の方の回答にあるLinux環境でも再現するはずです。

そういった同一要素を多数含む配列の場合、`partition2()`はほぼ1:1で2等分しO(N log
N)で処理できますが、`partition()`はlowかhighに近いインデックスで分割し1:N-1の分割しかできません。結果として`quickSort()`はO(N^2)に近くなってしまいます。

例えば同一値が7要素の `[0, 0, 0, 0, 0, 0, 0]`
をソートする場合、p1ではピボット値以外の要素以外はピボット値以上側に割り振られ21回比較が発生します。

[code]

    [] (0) [0, 0, 0, 0, 0, 0] // 比較6回
    [] (0) [[] (0) [0, 0, 0, 0, 0]] // 比較5回
    [] (0) [[] (0) [[] (0) [0, 0, 0, 0]]] // 比較4回
    [] (0) [[] (0) [[] (0) [[] (0) [0, 0, 0]]]] // 比較3回
    [] (0) [[] (0) [[] (0) [[] (0) [[] (0) [0, 0]]]]] // 比較2回
    [] (0) [[] (0) [[] (0) [[] (0) [[] (0) [[] (0) [0]]]]]] // 比較1回
    
[/code]

p2では両端から挟み込むので、ピボット位置が中央にきて比較16回で済みます。

[code]

    [0, 0, 0, 0, 0, 0, 0] // 比較8回
    [0, 0, 0] 0 [0, 0, 0] // 比較4+4回
    [[0] 0 [0]] 0 [[0] 0 [0]]
    
[/code]

同一値についてはp2で対応可能ですが、[0, 1, 2, 3]や[3, 2, 1,
0]のような入力に対してはp1もp2もうまくいかないので実用上はさらに工夫が必要されていることが多いようです。


CC BY-SA 4.0
2019-01-31T12:20:29.463
52450
2019-02-01T04:40:45.630
2019-02-01T04:40:45.630
241
241
52329
answer


[Quick
Sort](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88)は1960年に[アントニー・ホーアさん](https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%B3%E3%83%88%E3%83%8B%E3%83%BC%E3%83%BB%E3%83%9B%E3%83%BC%E3%82%A2)が発表したものです。Communications
of the ACM Volume 4 Issue 7, July 1961 Page 321に掲載されています。

  * [Algorithm 63: partition](https://dl.acm.org/citation.cfm?id=366642)
  * [Algorithm 64: Quicksort](https://dl.acm.org/citation.cfm?id=366644)

記述はPascal言語ですので`go to`が多用されるなど細部は異なりますが、p2に近い実装になっていました。

* * *

p1の出典は分かりませんが、スワップコスト（`int`でなく大きな構造体など）や配列サイズ（大規模配列でなく任意のサイズで良好な性能が得られるなど）も踏まえて改良されたものではないでしょうか。


CC BY-SA 4.0
2019-02-01T02:49:23.660
52464
2019-02-01T02:49:23.660
4236
52329
answer


余談ついでに [c++](/questions/tagged/c%2b%2b "'c++' のタグが付いた質問を表示") にはテンプレートライブラリで
`std::sort` が実装されています。  
<https://cpprefjp.github.io/reference/algorithm/sort.html>

[c++11](/questions/tagged/c%2b%2b11 "'c++11' のタグが付いた質問を表示") より古いものは「平均して」 `O(N
log N)` と規定されているので、最悪オーダーが `O(N*N)` となる quicksort で実装されていても要件に合致します。

[c++11](/questions/tagged/c%2b%2b11 "'c++11' のタグが付いた質問を表示")
で「平均して」の文言が削除され、つまり常に `O(N log N)` とされました。これを実現するために、ほぼすべての
[c++11](/questions/tagged/c%2b%2b11 "'c++11' のタグが付いた質問を表示") 処理系は
[イントロソート](https://ja.wikipedia.org/wiki/%E3%82%A4%E3%83%B3%E3%83%88%E3%83%AD%E3%82%BD%E3%83%BC%E3%83%88)
を実装しているようです（ってかホントは逆で、イントロソートの有用性が広く知られたので「平均して」を取ることにしたらしい）

イントロソートは途中までクイックソート、再帰が深くなったらヒープソートに切り替える（と、クイックソートの最悪状況を避けられる）というアルゴリズムです。実際に
gcc/cygwin
の実装を見てみたところ、イントロソートで「ほぼソート」し、挿入ソートするという方法を取っていました。挿入ソートは「ほぼソート」済み状態のデータに対してきわめて高速であることが知られています。各種アルゴリズムの良いとこ取り＋デバッグ済みなので
`std::sort` をぜひ使いたいところです。

ちなみに、乱数の与え方を `a[i]=xor128();` と `a[i]=xor128()&0x7FFF;` と２つのパターンを用意して
`std::sort` に渡したところ、重複が多いであろう 15bit 値のほうが早く終了しました。


CC BY-SA 4.0
2019-02-01T07:42:01.977
52477
2019-02-01T07:42:01.977
8589
52329
answer