(QuickSort:GeeksforGeeksを参照)

QuickSortの大枠を、

/* 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)
    }
}

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

/* 以下 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' とする

というもの（iとjが共に前から後ろへ。VisuAlgo他いくつかのサイトで見かける）と、

/* 以下 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
}

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

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

実験

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

|     | 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 | 未計測|

使ったC++コード

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

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

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

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

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

10^7 件 において

|     | 0.1%| 0.4% | 0.5%
+-----+-----+------+------
| p1' | 7.4 | 11.6 | クラッシュ(スタック溢れ？)
| p2  | 4.5 |  4.5 | 4.5

使ったコード断片

解決事項

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