uCRT の qsort のソースを読む

**uCRT: Universal C Run Time library**

# はじめに

筆者の下記の記事では，.NET Framework の `Array.Sort` の謎の動作に悩まされた。

https://qiita.com/TETSURO1999/items/68422ff100dbecf2ff1a

というのも筆者の知っている C 言語の `qsort` の動作とかなり違っていたからだ。とはいえ，そもそも `qsort` の内部メカニズムについてよく知らないのも事実である。

# uCRT の qsort の意訳版を作る

通常 Visual Studio 2022 をインストールすると `qsort` のソースコード（uCRT）は下記フォルダに置かれる。

`C:\Program Files (x86)\Windows Kits\10\Source\10.0.26100.0\ucrt\stdlib\qsort.cpp`

とはいえ，そのまま読んでもさっぱり分からないので（加えて著作権の問題もあるので）アルゴリズムを自分なりに咀嚼し，整数配列のソートとして新たに作り直したものを掲載する。大して長くは無いのでまずは全文を示そう。

```c:int 型配列のソートに作り直したクイックソート
/* 001 */ typedef int     (*COMPARE)(int, int);
/* 002 */ #define STACK_SIZE  30
/* 003 */ static  void    swap(int *p, int *q) {
/* 004 */     int temp = *p;
/* 005 */     *p = *q;
/* 006 */     *q = temp;
/* 007 */ }
/* 008 */ void    qsort_ucrt(int *a, int len, COMPARE compare) {
/* 009 */     if(len < 2) return;
/* 010 */     int top_stack[STACK_SIZE];
/* 011 */     int end_stack[STACK_SIZE];
/* 012 */     int stack = 0;
/* 013 */     int top = 0;
/* 014 */     int end = len - 1;
/* 015 */ LOOP:
/* 016 */     int n = end - top + 1;
/* 017 */     if(n <= 8) {
/* 018 */         for(int e = end; e > top; e--) {
/* 019 */             int max = top;
/* 020 */             for(int i = top + 1; i <= e; i++)
/* 021 */                 if(compare(a[i], a[max]) > 0) max = i;
/* 022 */             swap(&a[max], &a[e]);
/* 023 */         }
/* 024 */     } else {
/* 025 */         int mid = top + n / 2;
/* 026 */         int t = top;
/* 027 */         int e = end;
/* 028 */         if(compare(a[top], a[mid]) > 0) swap(&a[top], &a[mid]);
/* 029 */         if(compare(a[top], a[end]) > 0) swap(&a[top], &a[end]);
/* 030 */         if(compare(a[mid], a[end]) > 0) swap(&a[mid], &a[end]);
/* 031 */         for(;;) {
/* 032 */             if(t <  mid) while(++t <  mid && compare(a[t], a[mid]) <= 0);
/* 033 */             if(t >= mid) while(++t <= end && compare(a[t], a[mid]) <= 0);
/* 034 */             while(--e > mid && compare(a[e], a[mid]) > 0);
/* 035 */             if(t > e) break;
/* 036 */             swap(&a[t], &a[e]);
/* 037 */             if(e == mid) mid = t;
/* 038 */         }
/* 039 */         e++;
/* 040 */         if(e >  mid) while(--e > mid && compare(a[e], a[mid]) == 0);
/* 041 */         if(e <= mid) while(--e > top && compare(a[e], a[mid]) == 0);
/* 042 */         if(e - top >= end - t) {
/* 043 */             if(top < e) {
/* 044 */                 top_stack[stack] = top;
/* 045 */                 end_stack[stack] = e;
/* 046 */                 stack++;
/* 047 */             }
/* 048 */             if(t < end) {
/* 049 */                 top = t;
/* 050 */                 goto LOOP;
/* 051 */             }
/* 052 */         } else {
/* 053 */             if(t < end) {
/* 054 */                 top_stack[stack] = t;
/* 055 */                 end_stack[stack] = end;
/* 056 */                 stack++;
/* 057 */             }
/* 058 */             if(top < e) {
/* 059 */                 end = e;
/* 060 */                 goto LOOP;
/* 061 */             }
/* 062 */         }
/* 063 */     }
/* 064 */     if(--stack >= 0) {
/* 065 */         top = top_stack[stack];
/* 066 */         end = end_stack[stack];
/* 067 */         goto LOOP;
/* 068 */     }
/* 069 */ }
```

# アルゴリズム解説

それでは意訳版コードを頭から解説していきたい。

## 1. 交換関数

まずは，交換関数 `swap()` だ。これは後ほど多用するので最初に紹介する。関数マクロで定義しても良かったが，昨今のＣコンパイラであればインライン展開してくれるだろう。

```c++:交換関数
/* 003 */ static  void    swap(int *p, int *q) {
/* 004 */     int temp = *p;
/* 005 */     *p = *q;
/* 006 */     *q = temp;
/* 007 */ }
```

## 2. ソート関数本体の冒頭部分

次にソート関数本体 `qsort_ucrt()` の冒頭部分である。引数は `int` 型の配列 `a[]` と配列の要素数 `len` ，そして比較関数 `compare` の三つのみである。比較関数の型は標準ライブラリのものと少し変えており，二つの `int` 型の整数を直接比較する。

クイックソートはまずピボットと呼ばれる基準値を選び，ピボットと大小比較することでソート対象となる配列を分割する。そして分割された配列それぞれにクイックソートを施していくため，再帰関数として実装するほうが作り易いはずだ。しかし，uCRT では関数呼び出しのオーバーヘッドを嫌ってか内部スタックを用意して `goto` 文によるループ処理で済ませている。内部スタックのサイズ `STACK_SIZE` は 32bit アーキテクチャなら 30 個も確保すれば十分であろう。

そして配列の要素数が 2 個未満のときは何もしないでリターンする。

```c++:ソート関数の冒頭～内部スタックの確保
/* 001 */ typedef int     (*COMPARE)(int, int);
/* 002 */ #define STACK_SIZE  30

/* 008 */ void    qsort_ucrt(int *a, int len, COMPARE compare) {
/* 009 */     if(len < 2) return;
/* 010 */     int top_stack[STACK_SIZE];
/* 011 */     int end_stack[STACK_SIZE];
/* 012 */     int stack = 0;
/* 013 */     int top = 0;
/* 014 */     int end = len - 1;
/* 015 */ LOOP:
```

## 3. 小型ソート

次は分割された配列の要素数が８個以下になると呼び出される小型ソート（原文は short sort）である。

```c++:小型ソート（選択ソートっぽい）
/* 016 */     int n = end - top + 1;
/* 017 */     if(n <= 8) {
/* 018 */         for(int e = end; e > top; e--) {
/* 019 */             int max = top;
/* 020 */             for(int i = top + 1; i <= e; i++)
/* 021 */                 if(compare(a[i], a[max]) > 0) max = i;
/* 022 */             swap(&a[max], &a[e]);
/* 023 */         }
/* 024 */     } else {
```

なお，コメントには「挿入ソート」が用いられると書いてある。

> An insertion sort for sorting short arrays.

しかしながら，筆者が見る限り「選択ソート」のように思える。

## 4. ピボット選択

次は，分割された要素数が 8 個より大きい場合に適用されるクイックソート本体部分である。クイックソートではピボットの選択が重要である。たまたま選んだピボット値が最大値または最小値であった場合，クイックソートの効率は最悪になってしまうからだ。これを避けるため先頭と末尾と中間の三点でサンプリングして，その中で最大値でも最小値でもない中央値をピボットに選び，`a[top] <= a[mid]` かつ `a[mid] <= a[end]` となるように並べ直す。

以後，`a[mid]` の値をピボットとして用いる。

```c++:ピボット選択
/* 025 */         int mid = top + n / 2;
/* 026 */         int t = top;
/* 027 */         int e = end;
/* 028 */         if(compare(a[top], a[mid]) > 0) swap(&a[top], &a[mid]);
/* 029 */         if(compare(a[top], a[end]) > 0) swap(&a[top], &a[end]);
/* 030 */         if(compare(a[mid], a[end]) > 0) swap(&a[mid], &a[end]);
```

## 5. ピボットを基準とした交換処理

次はピボットを基準としてピボット以下の値は配列の頭のほうに，ピボットより大きな値はお尻のほうに集めていく。

```c++:ピボットを基準とした交換処理
/* 031 */         for(;;) {
/* 032 */             if(t <  mid) while(++t <  mid && compare(a[t], a[mid]) <= 0);
/* 033 */             if(t >= mid) while(++t <= end && compare(a[t], a[mid]) <= 0);
/* 034 */             while(--e > mid && compare(a[e], a[mid]) > 0);
/* 035 */             if(t > e) break;
/* 036 */             swap(&a[t], &a[e]);
/* 037 */             if(e == mid) mid = t;
/* 038 */         }
```

先頭から探す `t` の検索範囲は `top + 1` から `end` までとし，ピボット `a[mid]` より大きな値を探す。`t` の `while` ループを二つに分割しているのは `a[mid] == a[mid]` という無駄な比較を避けるためである。

一方，末尾から探す `e` の探索範囲は `end - 1` から `mid + 1` までとし，ピボット `a[mid]` 以下の値を探して，`a[t]` と `a[e]` を交換する。

`for` ループの終了条件は `t > e` である。`t` は単調増加，`e` は単調減少していくので必ず終了する。

ここで注意すべきなのはピボットより大きな値，あるいはピボット以下の値が見つからなかった場合である。先頭から探索する `t` はピボットより大きな値が見つからなかった場合は `t = end + 1` となり，交換する前に `for` ループを終了するので問題ない。一方，末尾から検索する `e` はピボット以下の値が見つからなかった場合は `e = mid` となり，`t < e` であれば `for` ループを脱出しないので普通に交換が行われる。この場合はピボットの位置が移動したことになるので `mid = t` とする。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="640" height="160">
<g fill="black">
<path d="M32 32  h576 v1 h-576">
<path d="M32 64  h576 v1 h-576">
<path d="M32  32 v32 h1 v-32">
<path d="M64  32 v32 h1 v-32">
<path d="M96  32 v32 h1 v-32">
<path d="M128 32 v32 h1 v-32">
<path d="M160 32 v32 h1 v-32">
<path d="M224 32 v32 h1 v-32">
<path d="M256 32 v32 h1 v-32">
<path d="M288 32 v32 h1 v-32">
<path d="M320 32 v32 h1 v-32">
<path d="M352 32 v32 h1 v-32">
<path d="M384 32 v32 h1 v-32">
<path d="M512 32 v32 h1 v-32">
<path d="M544 32 v32 h1 v-32">
<path d="M576 32 v32 h1 v-32">
<path d="M608 32 v32 h1 v-32">
</g>
<g fill="red">
<circle cx="80"  cy="96"  r="4">
<path d="M80 96 h500 v4 l12 -4 v-1 l-12 -4 v4 h-500">
</g>
<g fill="blue">
<circle cx="560" cy="128" r="4">
<path d="M560 128 h-180 v4 l-12 -4 v-1 l12 -4 v4 h180">
</g>
<text x="37"  y="28" font-size="14" fill="black">top</text>
<text x="323" y="28" font-size="14" fill="black">mid</text>
<text x="578" y="28" font-size="14" fill="black">end</text>
<text x="78"  y="88" font-size="14" fill="red">t</text>
<text x="556" y="120" font-size="14" fill="blue">e</text>
</svg>
title
<$FIGURE>
図１　探索範囲
end title
@enduml
```

## 6. 三分割

次は初見では意味が分からなかった部分である。基本的にクイックソートは対象区間を二つに分割していくとされているが，本ソートでは三つに分割するのだ。

```c++:三分割
/* 039 */         e++;
/* 040 */         if(e >  mid) while(--e > mid && compare(a[e], a[mid]) == 0);
/* 041 */         if(e <= mid) while(--e > top && compare(a[e], a[mid]) == 0);
```

37行目終了時点で `t` および `e` の配置は次のようになっている。`t - e = 1` となる。

`[top, t - 1]`，すなわち `[top, e]` の範囲はピボット以下の値が集められ，`[e + 1, end]`，すなわち `[t, end]` の範囲はピボットより大きな値が集められている。つまり，この時点では区間は二分割されている。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="640" height="96">
<path d="M32 32 v32 h320 v-32" fill="pink">
<path d="M352 32 v32 h256 v-32" fill="lightblue">
<path d="M32 32 h576 v1 h-576" fill="black" />
<path d="M32 64 h576 v1 h-576" fill="black" />
<path d="M32  32 v32 h1 v-32" fill="black" />
<path d="M64  32 v32 h1 v-32" fill="black" />
<path d="M96  32 v32 h1 v-32" fill="black" />
<path d="M128 32 v32 h1 v-32" fill="black" />
<path d="M160 32 v32 h1 v-32" fill="black" />
<path d="M224 32 v32 h1 v-32" fill="black" />
<path d="M256 32 v32 h1 v-32" fill="black" />
<path d="M288 32 v32 h1 v-32" fill="black" />
<path d="M320 32 v32 h1 v-32" fill="black" />
<path d="M352 32 v32 h1 v-32" fill="black" />
<path d="M384 32 v32 h1 v-32" fill="black" />
<path d="M512 32 v32 h1 v-32" fill="black" />
<path d="M544 32 v32 h1 v-32" fill="black" />
<path d="M576 32 v32 h1 v-32" fill="black" />
<path d="M608 32 v32 h1 v-32" fill="black" />
<text x="37"  y="28" font-size="14" fill="black">top</text>
<text x="578" y="28" font-size="14" fill="black">end</text>
<text x="332"  y="28" font-size="14" fill="black">e</text>
<text x="366"  y="28" font-size="14" fill="black">t</text>
</svg>
title
<$FIGURE>
図２　37行目終了時点での配置
end title
@enduml
```

ところが区間 `[top, e]` の末尾にピボットと同じ値が連続する場合，その範囲はソート済みとして次のソート対象区間から外してしまうのだ。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="640" height="96">
<path d="M32 32 v32 h224 v-32" fill="pink">
<path d="M352 32 v32 h256 v-32" fill="lightblue">
<path d="M32 32 h576 v1 h-576" fill="black" />
<path d="M32 64 h576 v1 h-576" fill="black" />
<path d="M32  32 v32 h1 v-32" fill="black" />
<path d="M64  32 v32 h1 v-32" fill="black" />
<path d="M96  32 v32 h1 v-32" fill="black" />
<path d="M128 32 v32 h1 v-32" fill="black" />
<path d="M160 32 v32 h1 v-32" fill="black" />
<path d="M224 32 v32 h1 v-32" fill="black" />
<path d="M256 32 v32 h1 v-32" fill="black" />
<path d="M288 32 v32 h1 v-32" fill="black" />
<path d="M320 32 v32 h1 v-32" fill="black" />
<path d="M352 32 v32 h1 v-32" fill="black" />
<path d="M384 32 v32 h1 v-32" fill="black" />
<path d="M512 32 v32 h1 v-32" fill="black" />
<path d="M544 32 v32 h1 v-32" fill="black" />
<path d="M576 32 v32 h1 v-32" fill="black" />
<path d="M608 32 v32 h1 v-32" fill="black" />
<text x="37"  y="28" font-size="14" fill="black">top</text>
<text x="578" y="28" font-size="14" fill="black">end</text>
<text x="236"  y="28" font-size="14" fill="black">e</text>
<text x="366"  y="28" font-size="14" fill="black">t</text>
</svg>
title
<$FIGURE>
図３　40行目終了時点での配置
end title
@enduml
```
なお `while` ループを二つに分けている意味は前と同じで `a[mid] == a[mid]` という無駄な比較を避けるためである。

## 7. 再帰ジャンプ

次は少々長いが難しくはない。要は `[top, e]` と `[t, end]` の二つの区間のうち，狭いほうを先にソートするという意味だ。広いほうを内部スタックに積むので後回しになる。もちろん区間の要素数が 1 個未満の場合はソートしない。

```c++:再帰ジャンプ
/* 042 */         if(e - top >= end - t) {
/* 043 */             if(top < e) {
/* 044 */                 top_stack[stack] = top;
/* 045 */                 end_stack[stack] = e;
/* 046 */                 stack++;
/* 047 */             }
/* 048 */             if(t < end) {
/* 049 */                 top = t;
/* 050 */                 goto LOOP;
/* 051 */             }
/* 052 */         } else {
/* 053 */             if(t < end) {
/* 054 */                 top_stack[stack] = t;
/* 055 */                 end_stack[stack] = end;
/* 056 */                 stack++;
/* 057 */             }
/* 058 */             if(top < e) {
/* 059 */                 end = e;
/* 060 */                 goto LOOP;
/* 061 */             }
/* 062 */         }
/* 063 */     }
/* 064 */     if(--stack >= 0) {
/* 065 */         top = top_stack[stack];
/* 066 */         end = end_stack[stack];
/* 067 */         goto LOOP;
/* 068 */     }
/* 069 */ }
```

# 感想

よく出来ている。芸術品である・・・と，この記事を書いた当時はそう思っていた。