Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 1136] ファイルの概要

このコミットは、Go言語の標準ライブラリであるsortパッケージにおけるクイックソートの実装を大幅に改善するものです。特に、BentleyとMcIlroyによる1993年の論文「Engineering a Sort Function」で提案された手法を取り入れ、ソートの堅牢性とパフォーマンスを向上させています。具体的には、「ninther」によるピボット選択と、全要素が同じ値の配列に対する二次的な振る舞いを避けるための「三方向分割（three-way partition）」が導入されています。また、パッケージ名がSortからsortに変更され、Goの命名規則に合わせられています。

コミット

commit 5aa7dc5daf821d1bdacde2fe23523a5406c70e8e
Author: Russ Cox <rsc@golang.org>
Date:   Mon Nov 17 11:51:34 2008 -0800

    adopt suggestions from Bentley and McIlroy (SP&E Nov 1993)
    to make qsort more robust:
    
            * use "ninther" to choose pivot.
            * use three-way partition to avoid quadratic
              behavior on all-one-value arrays.
    
    also add tests suggested in that paper.
    
    the immediate cause of the slowness we observed was
    in fact none of these: the recursive call was sorting
    data[0:m] instead of data[a:m].
    
    also rename package to "sort" to match convention.
    
    R=r,gri
    DELTA=358  (255 added, 21 deleted, 82 changed)
    OCL=19341
    CL=19373
---
 src/lib/sort.go | 127 ++++++++++++++++++++++++--------
 test/sorting.go | 225 ++++++++++++++++++++++++++++++++++++++++++++++++--------
 2 files changed, 293 insertions(+), 59 deletions(-)

diff --git a/src/lib/sort.go b/src/lib/sort.go
index fb5f77f471..381388223f 100644
--- a/src/lib/sort.go
+++ b/src/lib/sort.go
@@ -2,7 +2,7 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-package Sort
+package sort
 
 export type SortInterface interface {
 	len() int;
@@ -10,43 +10,112 @@ export type SortInterface interface {
 	swap(i, j int);\n}\n \n-\n-func Pivot(data SortInterface, a, b int) int {\n-\t// if we have at least 10 elements, find a better median\n-\t// by selecting the median of 3 elements and putting it\n-\t// at position a\n-\tif b - a >= 10 {\n-\t\tm0 := (a + b) / 2;\n-\t\tm1 := a;\n-\t\tm2 := b - 1;\n-\t\t// bubble sort on 3 elements\n-\t\tif data.less(m1, m0) { data.swap(m1, m0); }\n-\t\tif data.less(m2, m1) { data.swap(m2, m1); }\n-\t\tif data.less(m1, m0) { data.swap(m1, m0); }\n-\t\t// \"m0 <= m1 <= m2\"\n+\t}\n-\t\n-\tm := a;\n-\tfor i := a + 1; i < b; i++ {\n-\t\tif data.less(i, a) {\n-\t\t\tm++;\n-\t\t\tdata.swap(i, m);\n+\treturn b;\n+}\n+\n+// Insertion sort\n+func InsertionSort(data SortInterface, a, b int) {\n+\tfor i := a+1; i < b; i++ {\n+\t\tfor j := i; j > a && data.less(j, j-1); j-- {\n+\t\t\tdata.swap(j, j-1);\n \t\t}\n \t}\n-\tdata.swap(a, m);\n-\t\n-\treturn m;\n }\n \n+// Quicksort, following Bentley and McIlroy,\n+// ``Engineering a Sort Function,\'\' SP&E November 1993.\n \n-func Quicksort(data SortInterface, a, b int) {\n-\tif a + 1 < b {\n-\t\tm := Pivot(data, a, b);\n-\t\tQuicksort(data, 0, m);\n-\t\tQuicksort(data, m + 1, b);\n+// Move the median of the three values data[a], data[b], data[c] into data[a].\n+func MedianOfThree(data SortInterface, a, b, c int) {\n+\tm0 := b;\n+\tm1 := a;\n+\tm2 := c;\n+\n+\t// bubble sort on 3 elements\n+\tif data.less(m1, m0) { data.swap(m1, m0); }\n+\tif data.less(m2, m1) { data.swap(m2, m1); }\n+\tif data.less(m1, m0) { data.swap(m1, m0); }\n+\t// now data[m0] <= data[m1] <= data[m2]\n+}\n+\n+func SwapRange(data SortInterface, a, b, n int) {\n+\tfor i := 0; i < n; i++ {\n+\t\tdata.swap(a+i, b+i);\n \t}\n }\n \n+func Pivot(data SortInterface, lo, hi int) (midlo, midhi int) {\n+\tm := (lo+hi)/2;\n+\tif hi - lo > 40 {\n+\t\t// Tukey\'s ``Ninther,\'\' median of three medians of three.\n+\t\ts := (hi - lo) / 8;\n+\t\tMedianOfThree(data, lo, lo+s, lo+2*s);\n+\t\tMedianOfThree(data, m, m-s, m+s);\n+\t\tMedianOfThree(data, hi-1, hi-1-s, hi-1-2*s);\n+\t}\n+\tMedianOfThree(data, lo, m, hi-1);\n+\n+\t// Invariants are:\n+\t//\tdata[lo] = pivot (set up by ChoosePivot)\n+\t//\tdata[lo <= i < a] = pivot\n+\t//\tdata[a <= i < b] < pivot\n+\t//\tdata[b <= i < c] is unexamined\n+\t//\tdata[c <= i < d] > pivot\n+\t//\tdata[d <= i < hi] = pivot\n+\t//\n+\t// Once b meets c, can swap the \"= pivot\" sections\n+\t// into the middle of the array.\n+\tpivot := lo;\n+\ta, b, c, d := lo+1, lo+1, hi, hi;\n+\tfor b < c {\n+\t\tif data.less(b, pivot) {\t// data[b] < pivot\n+\t\t\tb++;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif !data.less(pivot, b) {\t// data[b] = pivot\n+\t\t\tdata.swap(a, b);\n+\t\t\ta++;\n+\t\t\tb++;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif data.less(pivot, c-1) {\t// data[c-1] > pivot\n+\t\t\tc--;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif !data.less(c-1, pivot) {\t// data[c-1] = pivot\n+\t\t\tdata.swap(c-1, d-1);\n+\t\t\tc--;\n+\t\t\td--;\n+\t\t\tcontinue;\n+\t\t}\n+\t\t// data[b] > pivot; data[c-1] < pivot\n+\t\tdata.swap(b, c-1);\n+\t\tb++;\n+\t\tc--;\n+\t}\n+\n+\tn := min(b-a, a-lo);\n+\tSwapRange(data, lo, b-n, n);\n+\n+\tn = min(hi-d, d-c);\n+\tSwapRange(data, c, hi-n, n);\n+\n+\treturn lo+b-a, hi-(d-c);\n+}\n+\n+func Quicksort(data SortInterface, a, b int) {\n+\tif b - a > 7 {\n+\t\tmlo, mhi := Pivot(data, a, b);\n+\t\tQuicksort(data, a, mlo);\n+\t\tQuicksort(data, mhi, b);\n+\t} else if b - a > 1 {\n+\t\tInsertionSort(data, a, b);\n+\t}\n+}\n \n export func Sort(data SortInterface) {\n \tQuicksort(data, 0, data.len());\ndiff --git a/test/sorting.go b/test/sorting.go
index ae9dafb751..ae278141f8 100644
--- a/test/sorting.go
+++ b/test/sorting.go
@@ -6,13 +6,19 @@
 
 package main
 
-import Sort "sort"\n+import (\n+\t\"fmt\";\n+\t\"rand\";\n+\t\"sort\";\n+)\n+\n+func BentleyMcIlroyTests();\n \n func main() {\n \t{\tdata := []int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586};\n-\t\ta := Sort.IntArray{&data};\n-\t\t\n-\t\tSort.Sort(&a);\n+\t\ta := sort.IntArray{&data};\n+\n+\t\tsort.Sort(&a);\
 \n \t\t/*\n \t\tfor i := 0; i < len(data); i++ {\n@@ -20,16 +26,16 @@ func main() {\n \t\t}\n \t\tprint(\"\\n\");\n \t\t*/\n-\t\t\n-\t\tif !Sort.IsSorted(&a) {\n+\n+\t\tif !sort.IsSorted(&a) {\n \t\t\tpanic();\n \t\t}\n \t}\n \n \t{\tdata := []float{74.3, 59.0, 238.2, -784.0, 2.3, 9845.768, -959.7485, 905, 7.8, 7.8};\n-\t\ta := Sort.FloatArray{&data};\n-\t\t\n-\t\tSort.Sort(&a);\n+\t\ta := sort.FloatArray{&data};\n+\n+\t\tsort.Sort(&a);\
 \n \t\t/*\n \t\tfor i := 0; i < len(data); i++ {\n@@ -37,16 +43,16 @@ func main() {\n \t\t}\n \t\tprint(\"\\n\");\n \t\t*/\n-\t\t\n-\t\tif !Sort.IsSorted(&a) {\n+\n+\t\tif !sort.IsSorted(&a) {\n \t\t\tpanic();\n \t\t}\n \t}\n \n \t{\tdata := []string{\"\", \"Hello\", \"foo\", \"bar\", \"foo\", \"f00\", \"%*&^*&^&\", \"***\"};\n-\t\ta := Sort.StringArray{&data};\n-\t\t\n-\t\tSort.Sort(&a);\n+\t\ta := sort.StringArray{&data};\n+\n+\t\tsort.Sort(&a);\
 \n \t\t/*\n \t\tfor i := 0; i < len(data); i++ {\n@@ -54,17 +60,17 @@ func main() {\n \t\t}\n \t\tprint(\"\\n\");\n \t\t*/\n-\t\t\n-\t\tif !Sort.IsSorted(&a) {\n+\n+\t\tif !sort.IsSorted(&a) {\n \t\t\tpanic();\n \t\t}\n \t}\n-\t\n+\n \t// Same tests again, this time using the convenience wrappers\n-\t\n+\n \t{\tdata := []int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586};\n-\t\t\n-\t\tSort.SortInts(&data);\n+\n+\t\tsort.SortInts(&data);\
 \n \t\t/*\n \t\tfor i := 0; i < len(data); i++ {\n@@ -72,15 +78,15 @@ func main() {\n \t\t}\n \t\tprint(\"\\n\");\n \t\t*/\n-\t\t\n-\t\tif !Sort.IntsAreSorted(&data) {\n+\n+\t\tif !sort.IntsAreSorted(&data) {\n \t\t\tpanic();\n \t\t}\n \t}\n \n \t{\tdata := []float{74.3, 59.0, 238.2, -784.0, 2.3, 9845.768, -959.7485, 905, 7.8, 7.8};\n-\t\t\n-\t\tSort.SortFloats(&data);\n+\n+\t\tsort.SortFloats(&data);\
 \n \t\t/*\n \t\tfor i := 0; i < len(data); i++ {\n@@ -88,15 +94,15 @@ func main() {\n \t\t}\n \t\tprint(\"\\n\");\n \t\t*/\n-\t\t\n-\t\tif !Sort.FloatsAreSorted(&data) {\n+\n+\t\tif !sort.FloatsAreSorted(&data) {\n \t\t\tpanic();\n \t\t}\n \t}\n \n \t{\tdata := []string{\"\", \"Hello\", \"foo\", \"bar\", \"foo\", \"f00\", \"%*&^*&^&\", \"***\"};\n-\t\t\n-\t\tSort.SortStrings(&data);\n+\n+\t\tsort.SortStrings(&data);\
 \n \t\t/*\n \t\tfor i := 0; i < len(data); i++ {\n@@ -104,9 +110,168 @@ func main() {\n \t\t}\n \t\tprint(\"\\n\");\n \t\t*/\n-\t\t\n-\t\tif !Sort.StringsAreSorted(&data) {\n+\n+\t\tif !sort.StringsAreSorted(&data) {\n \t\t\tpanic();\n \t\t}\n \t}\n+\n+\t{\n+\t\tdata := new([]int, 100000);\n+\t\tfor i := 0; i < len(data); i++ {\n+\t\t\tdata[i] = rand.rand() % 100;\n+\t\t}\n+\t\tif sort.IntsAreSorted(data) {\n+\t\t\tpanic(\"terrible rand.rand\");\n+\t\t}\n+\t\tsort.SortInts(data);\n+\t\tif !sort.IntsAreSorted(data) {\n+\t\t\tpanic();\n+\t\t}\n+\t}\n+\n+\tBentleyMcIlroyTests();\n+}\n+\n+const (\n+\tSawtooth = iota;\n+\tRand;\n+\tStagger;\n+\tPlateau;\n+\tShuffle;\n+\tNDist;\n+)\n+\n+const (\n+\tCopy = iota;\n+\tReverse;\n+\tReverseFirstHalf;\n+\tReverseSecondHalf;\n+\tSort;\n+\tDither;\n+\tNMode;\n+);\n+\n+type TestingData struct {\n+\tdata *[]int;\n+\tmaxswap int;\t// number of swaps allowed\n+\tnswap int;\n+}\n+\n+func (d *TestingData) len() int { return len(d.data); }\n+func (d *TestingData) less(i, j int) bool { return d.data[i] < d.data[j]; }\n+func (d *TestingData) swap(i, j int) {\n+\tif d.nswap >= d.maxswap {\n+\t\tpanicln(\"used\", d.nswap, \"swaps sorting\", len(d.data), \"array\");\n+\t}\n+\td.nswap++;\n+\td.data[i], d.data[j] = d.data[j], d.data[i];\n+}\n+\n+func Lg(n int) int {\n+\ti := 0;\n+\tfor 1<<uint(i) < n {\n+\t\ti++;\n+\t}\n+\treturn i;\n+}\n+\n+func Min(a, b int) int {\n+\tif a < b {\n+\t\treturn a;\n+\t}\n+\treturn b;\n+}\n+\n+func SortIntsTest(mode int, data, x *[]int) {\n+\tswitch mode {\n+\tcase Copy:\n+\t\tfor i := 0; i < len(data); i++ {\n+\t\t\tx[i] = data[i];\n+\t\t}\n+\tcase Reverse:\n+\t\tfor i := 0; i < len(data); i++ {\n+\t\t\tx[i] = data[len(data)-i-1];\n+\t\t}\n+\tcase ReverseFirstHalf:\n+\t\tn := len(data)/2;\n+\t\tfor i := 0; i < n; i++ {\n+\t\t\tx[i] = data[n-i-1];\n+\t\t}\n+\t\tfor i := n; i < len(data); i++ {\n+\t\t\tx[i] = data[i];\n+\t\t}\n+\tcase ReverseSecondHalf:\n+\t\tn := len(data)/2;\n+\t\tfor i := 0; i < n; i++ {\n+\t\t\tx[i] = data[i];\n+\t\t}\n+\t\tfor i := n; i < len(data); i++ {\n+\t\t\tx[i] = data[len(data)-(i-n)-1];\n+\t\t}\n+\tcase Sort:\n+\t\tfor i := 0; i < len(data); i++ {\n+\t\t\tx[i] = data[i];\n+\t\t}\n+\t\t// sort.SortInts is known to be correct\n+\t\t// because mode Sort runs after mode Copy.\n+\t\tsort.SortInts(x[0:len(data)]);\n+\tcase Dither:\n+\t\tfor i := 0; i < len(data); i++ {\n+\t\t\tx[i] = data[i] + i%5;\n+\t\t}\n+\t}\n+\td := &TestingData{x[0:len(data)], len(data)*Lg(len(data))*12/10, 0};\n+\tsort.Sort(d);\n+\n+\t// If we were testing C qsort, we\'d have to make a copy\n+\t// of the array and sort it ourselves and then compare\n+\t// x against it, to ensure that qsort was only permuting\n+\t// the data, not (for example) overwriting it with zeros.\n+\t//\n+\t// In go, we don\'t have to be so paranoid: since the only\n+\t// mutating method sort.Sort can call is TestingData.swap,\n+\t// it suffices here just to check that the final array is sorted.\n+\tif !sort.IntsAreSorted(x[0:len(data)]) {\n+\t\tpanicln(\"incorrect sort\");\n+\t}\n }\n+\n+func BentleyMcIlroyTests() {\n+\tsizes := []int{100, 1023, 1024, 1025};\n+\tvar x, tmp [1025]int;\n+\tfor ni := 0; ni < len(sizes); ni++ {\n+\t\tn := sizes[ni];\n+\t\tfor m := 1; m < 2*n; m *= 2 {\n+\t\t\tfor dist := 0; dist < NDist; dist++ {\n+\t\t\t\tj := 0;\n+\t\t\t\t\tk := 1;\n+\t\t\t\tfor i := 0; i < n; i++ {\n+\t\t\t\t\tswitch dist {\n+\t\t\t\t\tcase Sawtooth:\n+\t\t\t\t\t\tx[i] = i % m;\n+\t\t\t\t\tcase Rand:\n+\t\t\t\t\t\tx[i] = rand.rand() % m;\n+\t\t\t\t\tcase Stagger:\n+\t\t\t\t\t\tx[i] = (i*m + i) % n;\n+\t\t\t\t\tcase Plateau:\n+\t\t\t\t\t\tx[i] = Min(i, m);\n+\t\t\t\t\tcase Shuffle:\n+\t\t\t\t\t\tif rand.rand() % m != 0 {\n+\t\t\t\t\t\t\tj += 2;\n+\t\t\t\t\t\t\tx[i] = j;\n+\t\t\t\t\t\t} else {\n+\t\t\t\t\t\t\tk += 2;\n+\t\t\t\t\t\t\tx[i] = k;\n+\t\t\t\t\t\t}\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t\tdata := (&x)[0:n];\n+\t\t\t\tfor i := 0; i < NMode; i++ {\n+\t\t\t\t\tSortIntsTest(i, data, &tmp);\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\t}\n+}\n+\n```

## GitHub上でのコミットページへのリンク

[https://github.com/golang/go/commit/5aa7dc5daf821d1bdacde2fe23523a5406c70e8e](https://github.com/golang/go/commit/5aa7dc5daf821d1bdacde2fe23523a5406c70e8e)

## 元コミット内容

adopt suggestions from Bentley and McIlroy (SP&E Nov 1993) to make qsort more robust:

    * use "ninther" to choose pivot.
    * use three-way partition to avoid quadratic
      behavior on all-one-value arrays.

also add tests suggested in that paper.

the immediate cause of the slowness we observed was in fact none of these: the recursive call was sorting data[0:m] instead of data[a:m].

also rename package to "sort" to match convention.

R=r,gri DELTA=358 (255 added, 21 deleted, 82 changed) OCL=19341 CL=19373


## 変更の背景

このコミットの背景には、Go言語の`sort`パッケージにおけるクイックソートの実装が特定のシナリオでパフォーマンス上の問題（遅さ）を抱えていたという認識があります。コミットメッセージによると、直接的な遅さの原因は、再帰呼び出しが`data[0:m]`をソートすべきところを`data[a:m]`をソートしていたというバグであったと述べられています。

しかし、それとは別に、クイックソート自体の堅牢性と効率性を向上させる必要性も認識されていました。特に、BentleyとMcIlroyが1993年に発表した論文「Engineering a Sort Function」で提唱された、より洗練されたピボット選択戦略とパーティショニング（分割）戦略を導入することで、最悪ケースのパフォーマンスを改善し、より幅広いデータセットに対して安定した性能を発揮することを目指しました。

具体的には、以下の問題に対処するために変更が加えられました。

1.  **ピボット選択の改善**: 従来のクイックソートでは、ピボットの選択が悪いと（例えば、常に最小値や最大値が選ばれると）、ソートの計算量がO(N log N)からO(N^2)に劣化する可能性があります。特に、既にソートされている、逆順にソートされている、または多くの重複値を含むデータセットでこの問題が発生しやすくなります。
2.  **重複値の多い配列でのパフォーマンス劣化**: 全ての要素が同じ値であるような配列（または非常に多くの重複値を含む配列）に対して、従来の二方向分割（two-way partition）のクイックソートは、要素がピボットと同じ値である場合でも、それらをどちらかのパーティションに寄せてしまうため、再帰呼び出しの深さが不必要に増大し、O(N^2)の計算量に陥る可能性がありました。
3.  **Goの命名規則への準拠**: パッケージ名が`Sort`から`sort`へと変更され、Go言語の標準的な命名規則（パッケージ名は小文字で記述する）に合わせられました。

これらの改善により、`sort`パッケージのクイックソートは、より堅牢で効率的なソートアルゴリズムとして機能するようになりました。

## 前提知識の解説

### クイックソート (Quicksort)

クイックソートは、C.A.R. Hoareによって開発された効率的なソートアルゴリズムです。分割統治法（Divide and Conquer）に基づいています。

1.  **ピボットの選択**: 配列の中から「ピボット」と呼ばれる要素を一つ選びます。
2.  **パーティショニング（分割）**: ピボットを基準に配列を分割します。ピボットより小さい要素はピボットの左側に、大きい要素は右側に移動させます。ピボットは最終的なソート位置に配置されます。
3.  **再帰**: 分割された二つのサブ配列に対して、再帰的にクイックソートを適用します。

平均的な計算量はO(N log N)ですが、最悪ケースではO(N^2)になることがあります。最悪ケースは、ピボットの選択が常に極端な値（最小値や最大値）になる場合に発生します。

### ピボット選択戦略

クイックソートのパフォーマンスは、ピボットの選択に大きく依存します。

*   **ランダム選択**: 配列からランダムに要素を選ぶ方法。平均的には良い性能を示しますが、運が悪いと最悪ケースに陥る可能性があります。
*   **中央値の選択 (Median-of-three)**: 配列の最初、中央、最後の3つの要素の中から中央値を選び、それをピボットとして使用する方法。これにより、極端なピボットが選ばれる可能性を減らし、最悪ケースの発生頻度を低減します。
*   **Ninther (Median-of-three medians of three)**: BentleyとMcIlroyの論文で提案された、より洗練されたピボット選択戦略です。配列を3つの部分に分け、それぞれの部分から中央値を選び、さらにその3つの中央値の中から中央値を選ぶ方法です。これにより、さらに良いピボットが選ばれる可能性が高まり、最悪ケースの発生をさらに抑制します。

### 三方向分割 (Three-way Partitioning / Dutch National Flag Problem)

通常のクイックソートのパーティショニングは、ピボットより小さい要素と大きい要素の2つのグループに分割します。しかし、配列内にピボットと同じ値の要素が多数存在する場合、これらの要素がどちらかのグループに偏ってしまい、再帰呼び出しの深さが増大し、パフォーマンスがO(N^2)に劣化する可能性があります。

三方向分割は、配列を以下の3つのグループに分割します。

1.  ピボットより小さい要素
2.  ピボットと同じ要素
3.  ピボットより大きい要素

これにより、ピボットと同じ値の要素は再帰呼び出しの対象から外れるため、重複値が多い配列に対してもO(N log N)のパフォーマンスを維持できます。これは、Edsger W. Dijkstraによって「オランダの国旗問題（Dutch National Flag Problem）」として知られる問題の解決策としても知られています。

### Go言語の `sort` パッケージと `SortInterface`

Go言語の標準ライブラリには、ソート機能を提供する`sort`パッケージがあります。このパッケージは、特定の型に依存しない汎用的なソート機能を提供するために`sort.Interface`というインターフェースを定義しています。

`sort.Interface`は以下の3つのメソッドを持ちます。

*   `Len() int`: ソート対象の要素数を返します。
*   `Less(i, j int) bool`: インデックス`i`の要素がインデックス`j`の要素より小さい場合に`true`を返します。
*   `Swap(i, j int)`: インデックス`i`と`j`の要素を入れ替えます。

このインターフェースを実装することで、任意のデータ型を`sort.Sort`関数でソートできるようになります。

## 技術的詳細

このコミットでは、Go言語の`sort`パッケージにおけるクイックソートの実装が、BentleyとMcIlroyの論文に基づき、以下の主要な技術的改善が施されています。

1.  **Nintherピボット選択の導入**:
    *   新しい`Pivot`関数内で、配列のサイズが40より大きい場合に「Ninther」ピボット選択戦略が適用されます。
    *   Nintherは、「3つの中央値の3つの中央値」を意味します。具体的には、配列を8つのセグメントに分割し、それぞれのセグメントから3つの要素を選び、その中央値を計算します。そして、その3つの中央値の中からさらに中央値を選び、それを最終的なピボットとして使用します。
    *   これにより、ピボットが配列全体の中央値に近い値になる可能性が高まり、クイックソートの最悪ケース（O(N^2)）の発生を大幅に抑制します。
    *   `MedianOfThree`関数が新しく導入され、3つの要素の中央値を効率的に選択し、指定された位置に配置する役割を担います。

2.  **三方向分割 (Three-way Partitioning) の実装**:
    *   新しい`Pivot`関数は、ピボットを基準に配列を3つの部分に分割する三方向分割ロジックを含んでいます。
    *   分割された3つの領域は以下の通りです。
        *   `data[lo <= i < midlo]`: ピボットより小さい要素
        *   `data[midlo <= i < midhi]`: ピボットと同じ要素
        *   `data[midhi <= i < hi]`: ピボットより大きい要素
    *   この分割により、ピボットと同じ値の要素は中央の領域に集められ、再帰呼び出しの対象から除外されます。これにより、全ての要素が同じ値であるような配列に対しても、クイックソートがO(N log N)の計算量を維持できるようになります。
    *   パーティショニングの過程で、`data.less(b, pivot)`（`data[b]`がピボットより小さい）、`!data.less(pivot, b)`（`data[b]`がピボットと同じ）、`data.less(pivot, c-1)`（`data[c-1]`がピボットより大きい）、`!data.less(c-1, pivot)`（`data[c-1]`がピボットと同じ）といった条件を評価し、要素を適切にスワップしながら領域を拡張していきます。
    *   `SwapRange`関数が新しく導入され、指定された範囲の要素を効率的にスワップするのに使用されます。

3.  **小規模配列に対する挿入ソート (Insertion Sort) への切り替え**:
    *   `Quicksort`関数内で、ソート対象の配列のサイズが7以下の場合（`b - a <= 7`）、クイックソートの代わりに挿入ソートが使用されるようになりました。
    *   挿入ソートは、小規模な配列に対してはクイックソートよりもオーバーヘッドが少なく、効率的であるため、この最適化は全体的なパフォーマンス向上に寄与します。

4.  **パッケージ名の変更**:
    *   `src/lib/sort.go`のパッケージ名が`Sort`から`sort`に変更されました。これはGo言語の命名規則（パッケージ名は小文字で記述する）に準拠するための変更です。

5.  **テストの追加**:
    *   `test/sorting.go`に、BentleyとMcIlroyの論文で提案されたテストケースが追加されました。これらのテストは、様々なデータ分布（のこぎり波、ランダム、千鳥、プラトー、シャッフルなど）と操作モード（コピー、逆順、ソート済みなど）に対してソートアルゴリズムの堅牢性とパフォーマンスを検証します。
    *   `TestingData`構造体が導入され、ソート中のスワップ回数をカウントすることで、アルゴリズムの効率性を間接的に評価できるようになっています。

これらの変更により、Goの`sort`パッケージは、より堅牢で高性能なソート機能を提供するようになりました。

## コアとなるコードの変更箇所

このコミットにおけるコアとなるコードの変更箇所は、主に`src/lib/sort.go`と`test/sorting.go`の2つのファイルに集中しています。

### `src/lib/sort.go`

*   **パッケージ名の変更**:
    ```diff
    --- a/src/lib/sort.go
    +++ b/src/lib/sort.go
    @@ -2,7 +2,7 @@
     // Use of this source code is governed by a BSD-style
     // license that can be found in the LICENSE file.
     
    -package Sort
    +package sort
     ```
    `Sort`から`sort`へパッケージ名が変更されました。

*   **`Pivot`関数の大幅な変更と新しいヘルパー関数の追加**:
    *   既存の単純な`Pivot`関数が削除され、BentleyとMcIlroyの論文に基づく新しい`Pivot`関数が導入されました。
    *   新しい`Pivot`関数は、Nintherピボット選択と三方向分割ロジックを実装しています。
    *   `MedianOfThree`関数が新しく追加され、3つの要素の中央値を効率的に選択します。
    *   `SwapRange`関数が新しく追加され、指定された範囲の要素をスワップします。
    *   `min`関数が追加されました。

*   **`Quicksort`関数の変更**:
    ```diff
    --- a/src/lib/sort.go
    +++ b/src/lib/sort.go
    @@ -50,11 +50,20 @@ func InsertionSort(data SortInterface, a, b int) {
     }
     
     // Quicksort, following Bentley and McIlroy,
     // ``Engineering a Sort Function,'' SP&E November 1993.
     
    -func Quicksort(data SortInterface, a, b int) {
    -	if a + 1 < b {
    -		m := Pivot(data, a, b);
    -		Quicksort(data, 0, m);
    -		Quicksort(data, m + 1, b);
    -	}
    +func Quicksort(data SortInterface, a, b int) {
    +	if b - a > 7 { // 配列サイズが7より大きい場合
    +		mlo, mhi := Pivot(data, a, b); // 新しいPivot関数を呼び出し、三方向分割の結果を受け取る
    +		Quicksort(data, a, mlo);      // ピボットより小さい部分を再帰的にソート
    +		Quicksort(data, mhi, b);      // ピボットより大きい部分を再帰的にソート
    +	} else if b - a > 1 { // 配列サイズが1より大きく7以下の場合
    +		InsertionSort(data, a, b); // 挿入ソートを使用
    +	}
     }
     ```
    `Quicksort`の再帰呼び出しの範囲が`data[0:m]`から`data[a:m]`に修正され、また、小規模な配列（サイズ7以下）に対しては`InsertionSort`を呼び出すように変更されました。

### `test/sorting.go`

*   **インポートの変更**:
    ```diff
    --- a/test/sorting.go
    +++ b/test/sorting.go
    @@ -6,13 +6,19 @@
     
     package main
     
    -import Sort "sort"
    +import (
    +	"fmt";
    +	"rand";
    +	"sort";
    +)
    +
    +func BentleyMcIlroyTests();
     ```
    `Sort`というエイリアスが削除され、標準の`sort`パッケージが直接インポートされるようになりました。また、`fmt`と`rand`パッケージが追加でインポートされています。

*   **既存テストのパッケージ名参照の修正**:
    既存のテストコード内で`Sort.IntArray`などが`sort.IntArray`に、`Sort.Sort(&a)`が`sort.Sort(&a)`に、`Sort.IsSorted(&a)`が`sort.IsSorted(&a)`に、`Sort.SortInts(&data)`が`sort.SortInts(&data)`に、`Sort.IntsAreSorted(&data)`が`sort.IntsAreSorted(&data)`にそれぞれ変更されました。

*   **Bentley-McIlroyテストの追加**:
    *   `BentleyMcIlroyTests()`関数が追加され、論文で提案された様々なテストケースを実行します。
    *   `TestingData`構造体とそれに関連する`len`, `less`, `swap`メソッドが追加され、ソート中のスワップ回数を追跡できるようになりました。
    *   `SortIntsTest`関数が追加され、様々なデータ分布と操作モードでソートをテストします。
    *   `Lg`（対数）と`Min`関数がヘルパーとして追加されました。

これらの変更により、ソートアルゴリズムの核心部分が改善され、その堅牢性を検証するための包括的なテストスイートが追加されました。

## コアとなるコードの解説

このコミットで導入されたクイックソートのコアとなるコードは、主に`src/lib/sort.go`内の`Quicksort`、`Pivot`、`MedianOfThree`、`SwapRange`、そして`InsertionSort`関数です。

### `Quicksort` 関数

```go
func Quicksort(data SortInterface, a, b int) {
	if b - a > 7 { // 配列サイズが7より大きい場合
		mlo, mhi := Pivot(data, a, b); // 新しいPivot関数を呼び出し、三方向分割の結果を受け取る
		Quicksort(data, a, mlo);      // ピボットより小さい部分を再帰的にソート
		Quicksort(data, mhi, b);      // ピボットより大きい部分を再帰的にソート
	} else if b - a > 1 { // 配列サイズが1より大きく7以下の場合
		InsertionSort(data, a, b); // 挿入ソートを使用
	}
}
  • 小規模配列の最適化: b - a > 7という条件は、ソート対象の要素数が7より大きい場合にのみクイックソートを適用することを示しています。要素数が7以下の場合（b - a > 1）、InsertionSortが呼び出されます。これは、小規模な配列では挿入ソートの方がクイックソートのオーバーヘッド（再帰呼び出し、ピボット選択など）なしに効率的であるためです。
  • 三方向分割の利用: Pivot関数が2つの戻り値mloとmhiを返すようになりました。これらは三方向分割によって得られた、ピボットと同じ値の要素の範囲を示します。
  • 再帰呼び出し: Quicksortは、data[a:mlo]（ピボットより小さい要素の範囲）とdata[mhi:b]（ピボットより大きい要素の範囲）に対して再帰的に呼び出されます。これにより、ピボットと同じ値の要素は再帰の対象から外れ、重複値が多い場合のパフォーマンス劣化を防ぎます。

Pivot 関数

func Pivot(data SortInterface, lo, hi int) (midlo, midhi int) {
	m := (lo+hi)/2;
	if hi - lo > 40 { // 配列サイズが40より大きい場合
		// Tukey's ``Ninther,'' median of three medians of three.
		s := (hi - lo) / 8;
		MedianOfThree(data, lo, lo+s, lo+2*s);
		MedianOfThree(data, m, m-s, m+s);
		MedianOfThree(data, hi-1, hi-1-s, hi-1-2*s);
	}
	MedianOfThree(data, lo, m, hi-1); // 最終的なピボットをloに配置

	// Invariants are:
	//  data[lo] = pivot (set up by ChoosePivot)
	//  data[lo <= i < a] = pivot
	//  data[a <= i < b] < pivot
	//  data[b <= i < c] is unexamined
	//  data[c <= i < d] > pivot
	//  data[d <= i < hi] = pivot
	//
	// Once b meets c, can swap the " = pivot" sections
	// into the middle of the array.
	pivot := lo;
	a, b, c, d := lo+1, lo+1, hi, hi;
	for b < c {
		if data.less(b, pivot) { // data[b] < pivot
			b++;
			continue;
		}
		if !data.less(pivot, b) { // data[b] = pivot
			data.swap(a, b);
			a++;
			b++;
			continue;
		}
		if data.less(pivot, c-1) { // data[c-1] > pivot
			c--;
			continue;
		}
		if !data.less(c-1, pivot) { // data[c-1] = pivot
			data.swap(c-1, d-1);
			c--;
			d--;
			continue;
			}
		// data[b] > pivot; data[c-1] < pivot
		data.swap(b, c-1);
		b++;
		c--;
	}

	n := min(b-a, a-lo);
	SwapRange(data, lo, b-n, n);

	n = min(hi-d, d-c);
	SwapRange(data, c, hi-n, n);

	return lo+b-a, hi-(d-c);
}
  • Nintherピボット選択: 配列のサイズが40より大きい場合、MedianOfThreeを複数回呼び出すことで「Ninther」戦略を実装し、より良いピボットを選択します。これにより、ピボットが極端な値になる可能性を減らします。
  • 三方向分割ロジック: a, b, c, dという4つのポインタ（インデックス）を使って、配列を「ピボットより小さい」「ピボットと同じ」「未検査」「ピボットより大きい」の4つの領域に分割します。ループが終了すると、ピボットと同じ値の要素が中央に集められ、その範囲[midlo, midhi)が返されます。
  • SwapRangeの利用: パーティショニングの最後に、SwapRange関数を使って、ピボットと同じ値の要素を配列の中央に移動させます。

MedianOfThree 関数

func MedianOfThree(data SortInterface, a, b, c int) {
	m0 := b;
	m1 := a;
	m2 := c;

	// bubble sort on 3 elements
	if data.less(m1, m0) { data.swap(m1, m0); }
	if data.less(m2, m1) { data.swap(m2, m1); }
	if data.less(m1, m0) { data.swap(m1, m0); }
	// now data[m0] <= data[m1] <= data[m2]
}

この関数は、与えられた3つのインデックスa, b, cに対応する要素を比較し、バブルソートの要領でそれらをソートします。最終的に、data[m0] <= data[m1] <= data[m2]となるように要素を配置し、m1（中央値）の要素がdata[a]に移動するようにPivot関数内で利用されます。

SwapRange 関数

func SwapRange(data SortInterface, a, b, n int) {
	for i := 0; i < n; i++ {
		data.swap(a+i, b+i);
	}
}

このヘルパー関数は、n個の要素を、開始インデックスaから開始インデックスbへ、またはその逆へスワップするために使用されます。Pivot関数内で、三方向分割によって分離されたピボットと同じ値の要素のブロックを、配列の中央に移動させる際に利用されます。

InsertionSort 関数

func InsertionSort(data SortInterface, a, b int) {
	for i := a+1; i < b; i++ {
		for j := i; j > a && data.less(j, j-1); j-- {
			data.swap(j, j-1);
		}
	}
}

これは標準的な挿入ソートの実装です。Quicksort関数から、小規模な配列のソートのために呼び出されます。

これらの関数が連携することで、Goのsortパッケージは、より堅牢で効率的なクイックソートの実装を提供し、様々なデータ分布に対して安定した高性能を発揮できるようになりました。

関連リンク

  • Bentley and McIlroy (SP&E Nov 1993) 論文: "Engineering a Sort Function" by Jon L. Bentley and M. Douglas McIlroy, published in Software—Practice and Experience, Vol. 23, No. 11, pages 1249–1265, in November 1993.

参考にした情報源リンク