uCRT: Universal C Run Time library
はじめに
筆者の下記の記事では，.NET Framework の Array.Sort の謎の動作に悩まされた。
というのも筆者の知っている 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
とはいえ，そのまま読んでもさっぱり分からないので（加えて著作権の問題もあるので）アルゴリズムを自分なりに咀嚼し，整数配列のソートとして新たに作り直したものを掲載する。大して長くは無いのでまずは全文を示そう。
/* 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() だ。これは後ほど多用するので最初に紹介する。関数マクロで定義しても良かったが，昨今のＣコンパイラであればインライン展開してくれるだろう。
/* 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 個未満のときは何もしないでリターンする。
/* 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）である。
/* 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] の値をピボットとして用いる。
/* 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. ピボットを基準とした交換処理
次はピボットを基準としてピボット以下の値は配列の頭のほうに，ピボットより大きな値はお尻のほうに集めていく。
/* 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 とする。
6. 三分割
次は初見では意味が分からなかった部分である。基本的にクイックソートは対象区間を二つに分割していくとされているが，本ソートでは三つに分割するのだ。
/* 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] の範囲はピボットより大きな値が集められている。つまり，この時点では区間は二分割されている。
ところが区間 [top, e] の末尾にピボットと同じ値が連続する場合，その範囲はソート済みとして次のソート対象区間から外してしまうのだ。
なお while ループを二つに分けている意味は前と同じで a[mid] == a[mid] という無駄な比較を避けるためである。
7. 再帰ジャンプ
次は少々長いが難しくはない。要は [top, e] と [t, end] の二つの区間のうち，狭いほうを先にソートするという意味だ。広いほうを内部スタックに積むので後回しになる。もちろん区間の要素数が 1 個未満の場合はソートしない。
/* 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 */ }
感想
よく出来ている。芸術品である・・・と，この記事を書いた当時はそう思っていた。