クイックソートの2種類の実装法で実行速度に顕著な違いが出る


([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 は同一要素含みの配列に弱い




クイックソートでは(ほぼ)ソート済みの配列や同一要素の配列に対して平均的な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もうまくいかないので実用上はさらに工夫が必要されていることが多いようです。




クイックソートでは(ほぼ)ソート済みの配列や同一要素の配列に対して平均的な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もうまくいかないので実用上はさらに工夫が必要されていることが多いようです。

