* once_aQSort
-(by [[K]], 2024.09.03)
** (1) ver.1.10 [2024.09.04] (244行)
#define aQSortFast(Mod, Typ, CmpFnc) ACat3(aQSortFast_, Mod, CmpFnc)
#define aQSort(Mod, Typ) ACat3(aQSort_, Mod, Typ)
// Mod: 1=a0, a1がある.
// Mod: 2=wがある.
// Mod: 4=関数は非インライン.
// Mod: 8=Typのかわりに一般サイズ.
// Mod:16=N=3の高速化を利用しない.
// Mod:32=double-selection-sortを使わない.
#longdef @ALongdef_QSortFast(@Mod, @Typ, @CmpFnc)
#if ((@Mod & 6) == 0)
#define @cmp(a, b, w) @CmpFnc(a, b)
#elif ((@Mod & 6) == 2)
#define @cmp(a, b, w) @CmpFnc(a, b, w)
#elif ((@Mod & 6) == 4)
#define @cmp(a, b, w) cmp_(a, b)
#elif ((@Mod & 6) == 6)
#define @cmp(a, b, w) cmp_(a, b, w)
#endif
#if ((@Mod & 15) == 0)
AStatic void aQSortFast(@Mod, @Typ, @CmpFnc)(@Typ *bas, AInt n)
#elif ((@Mod & 15) == 1)
AStatic void aQSortFast(@Mod, @Typ, @CmpFnc)(@Typ *bas, AInt n, @Typ *a0, @Typ *a1)
#elif ((@Mod & 15) == 2)
AStatic void aQSortFast(@Mod, @Typ, @CmpFnc)(@Typ *bas, AInt n, void *w)
#elif ((@Mod & 15) == 3)
AStatic void aQSortFast(@Mod, @Typ, @CmpFnc)(@Typ *bas, AInt n, @Typ *a0, @Typ *a1, void *w)
#elif ((@Mod & 15) == 4)
AStatic void aQSort(@Mod, @Typ)(@Typ *bas, AInt n, int (*cmp_)(const void *, const void *))
#elif ((@Mod & 15) == 5)
AStatic void aQSort(@Mod, @Typ)(@Typ *bas, AInt n, @Typ *a0, @Typ *a1, int (*cmp_)(const void *, const void *))
#elif ((@Mod & 15) == 6)
AStatic void aQSort(@Mod, @Typ)(@Typ *bas, AInt n, int (*cmp_)(const void *, const void *, void *), void *w)
#elif ((@Mod & 15) == 7)
AStatic void aQSort(@Mod, @Typ)(@Typ *bas, AInt n, @Typ *a0, @Typ *a1, int (*cmp_)(const void *, const void *, void *), void *w)
#elif ((@Mod & 15) == 12)
AStatic void aQSort(@Mod, @Typ)(void *bas_, AInt n, AInt sz, int (*cmp_)(const void *, const void *))
#elif ((@Mod & 15) == 13)
AStatic void aQSort(@Mod, @Typ)(void *bas_, AInt n, AInt sz, void *a0_, void *a1_, int (*cmp_)(const void *, const void *))
#elif ((@Mod & 15) == 14)
AStatic void aQSort(@Mod, @Typ)(void *bas_, AInt n, AInt sz, int (*cmp_)(const void *, const void *, void *), void *w)
#elif ((@Mod & 15) == 15)
AStatic void aQSort(@Mod, @Typ)(void *bas_, AInt n, AInt sz, void *a0_, void *a1_, int (*cmp_)(const void *, const void *, void *), void *w)
#endif
{
n--;
if (n <= 0) return; // N=1
#if ((@Mod & 8) != 0)
char *bas = bas_;
#if ((@Mod & 1) != 0)
char *a0 = a0_, *a1 = a1_;
#endif
#endif
#if ((@Mod & 1) != 0)
if (a1 <= bas) return;
#endif
#if ((@Mod & 8) == 0)
@Typ *bi = bas; @Typ *bj = bas + n; @Typ *bk; @Typ c;
#define @Step 1
#define @Swap2(x, y) c = *x; *x = *y; *y = c;
#define @Swap3(x, y, z) c = *x; *x = *y; *y = *z; *z = c;
#else
char *bi = bas, *bj = bas + n * sz, *bk, c;
AInt i;
#define @Step sz
#define @Swap2(x,y) for (i = 0; i < sz; i++) { c = x[i]; x[i] = y[i]; y[i] = c; }
#define @Swap3(x, y, z) for (i = 0; i < sz; i++) { c = x[i]; x[i] = y[i]; y[i] = z[i]; z[i] = c; }
#endif
#if ((@Mod & 1) != 0)
if (bj < a0) return;
#endif
if (n == 1) { // N=2
if (@cmp(bas, bj, w) > 0) { @Swap2(bas, bj) }
return;
}
#if ((@Mod & 16) == 0) // 高速化の必要がなければ、ここは省略してもよい.
if (n == 2) { // N=3, 比較2回.
n2: bk = bas + @Step;
if (@cmp(bas, bk, w) <= 0) {
if (@cmp(bk, bj, w) <= 0) { return; } // i<k<j
if (@cmp(bj, bas, w) <= 0) { @Swap3(bas, bj, bk) return; } // j<i<k
@Swap2(bk, bj) return; // i<j<k
}
if (@cmp(bj, bk, w) <= 0) { @Swap2(bi, bj) return; } // j<k<i
if (@cmp(bas, bj, w) <= 0) { @Swap2(bas, bk) return; } // k<i<j
@Swap3(bas, bk, bj) return; // k<j<i
}
#endif
#if ((@Mod & 32) == 0) // 高速化の必要がなければ、ここは省略してもよい.
if (n <= 10) { // N<=11
do {
AInt i;
bi = bas; bj = bas + @Step; bk = bj;
if (@cmp(bi, bj, w) > 0) { bi = bj; bj = bas; }
for (i = 2; i <= n; i++) {
bk += @Step;
if (@cmp(bi, bk, w) > 0) { bi = bk; }
if (@cmp(bj, bk, w) < 0) { bj = bk; }
}
@Swap2(bas, bi)
if (bj == bas) { bj = bi; }
@Swap2(bk, bj)
bas += @Step;
n -= 2;
#if ((@Mod & 16) == 0)
} while (n > 2);
if (n == 2) { bj = bas + @Step * 2; goto n2; }
#else
} while (n > 1);
#endif
if (n == 1) {
bj = bas + @Step; if (@cmp(bas, bj, w) > 0) { @Swap2(bas, bj) }
}
return;
}
#endif
#if ((@Mod & 8) == 0)
@Typ p[1];
bk = bas + (n >> 1);
if (@cmp(bi, bk, w) <= 0) { // bi, bj, bkの中から中央値を見つけてpに代入.
if (@cmp(bk, bj, w) <= 0) { *p = *bk; goto start; } // i<k<j
if (@cmp(bj, bi, w) <= 0) { *p = *bi; goto start; } // j<i<k
*p = *bj; goto start; // i<j<k
} // else {
if (@cmp(bj, bk, w) <= 0) { *p = *bk; goto start; } // j<k<i
if (@cmp(bi, bj, w) <= 0) { *p = *bi; goto start; } // k<i<j
*p = *bj; goto start; // k<j<i
//}
#else
char *p;
bk = bas + (n >> 1) * sz;
if (@cmp(bi, bk, w) <= 0) { // bi, bj, bkの中から中央値を見つけてpに代入.
if (@cmp(bk, bj, w) <= 0) { p = bk; goto start; } // i<k<j
if (@cmp(bj, bi, w) <= 0) { p = bi; goto start; } // j<i<k
p = bj; goto start; // i<j<k
} // else {
if (@cmp(bj, bk, w) <= 0) { p = bk; goto start; } // j<k<i
if (@cmp(bi, bj, w) <= 0) { p = bi; goto start; } // k<i<j
p = bj; goto start; // k<j<i
//}
#endif
do {
@Swap2(bi, bj)
#if ((@Mod & 8) != 0)
if (p == bi) { p = bj; } else if (p == bj) { p = bi; }
#endif
bi += @Step; bj -= @Step;
start:
while (@cmp(bi, p, w) < 0) bi += @Step;
while (@cmp(p, bj, w) < 0) bj -= @Step;
} while (bi < bj);
#if ((@Mod & 15) == 0)
aQSortFast(@Mod, @Typ, @CmpFnc)(bas, bi - bas); // basからbiの手前まで.
aQSortFast(@Mod, @Typ, @CmpFnc)(bj + 1, n + (bas - bj)); // bj + 1からbas + (N-1) まで.
// bas + n + 1 - (bj + 1) ==> n + (bas - bj)
#elif ((@Mod & 15) == 1)
aQSortFast(@Mod, @Typ, @CmpFnc)(bas, bi - bas, a0, a1);
aQSortFast(@Mod, @Typ, @CmpFnc)(bj + 1, n + (bas - bj), a0, a1);
#elif ((@Mod & 15) == 2)
aQSortFast(@Mod, @Typ, @CmpFnc)(bas, bi - bas, w);
aQSortFast(@Mod, @Typ, @CmpFnc)(bj + 1, n + (bas - bj), w);
#elif ((@Mod & 15) == 3)
aQSortFast(@Mod, @Typ, @CmpFnc)(bas, bi - bas, a0, a1, w);
aQSortFast(@Mod, @Typ, @CmpFnc)(bj + 1, n + (bas - bj), a0, a1, w);
#elif ((@Mod & 15) == 4)
aQSort(@Mod, @Typ)(bas, bi - bas, cmp_);
aQSort(@Mod, @Typ)(bj + 1, n + (bas - bj), cmp_);
#elif ((@Mod & 15) == 5)
aQSort(@Mod, @Typ)(bas, bi - bas, a0, a1, cmp_);
aQSort(@Mod, @Typ)(bj + 1, n + (bas - bj), a0, a1, cmp_);
#elif ((@Mod & 15) == 6)
aQSort(@Mod, @Typ)(bas, bi - bas, cmp_, w);
aQSort(@Mod, @Typ)(bj + 1, n + (bas - bj), cmp_, w);
#elif ((@Mod & 15) == 7)
aQSort(@Mod, @Typ)(bas, bi - bas, a0, a1, cmp_, w);
aQSort(@Mod, @Typ)(bj + 1, n + (bas - bj), a0, a1, cmp_, w);
#elif ((@Mod & 15) == 12)
aQSort(@Mod, @Typ)(bas, (bi - bas) / sz, sz, cmp_);
aQSort(@Mod, @Typ)(bj + sz, n - (bj - bas) / sz, sz, cmp_);
#elif ((@Mod & 15) == 13)
aQSort(@Mod, @Typ)(bas, (bi - bas) / sz, sz, a0, a1, cmp_);
aQSort(@Mod, @Typ)(bj + sz, n - (bj - bas) / sz, sz, a0, a1, cmp_);
#elif ((@Mod & 15) == 14)
aQSort(@Mod, @Typ)(bas, (bi - bas) / sz, sz, cmp_, w);
aQSort(@Mod, @Typ)(bj + sz, n - (bj - bas) / sz, sz, cmp_, w);
#elif ((@Mod & 15) == 15)
aQSort(@Mod, @Typ)(bas, (bi - bas) / sz, sz, a0, a1, cmp_, w);
aQSort(@Mod, @Typ)(bj + sz, n - (bj - bas) / sz, sz, a0, a1, cmp_, w);
#endif
}
#undef @cmp
#undef @Step
#undef @Swap2
#undef @Swap3
#endlongdef
typedef int32_t aQSort_i32;
typedef int64_t aQSort_i64;
#longuse ALongdef_QSortFast(4, aQSort_i32, _)
#longuse ALongdef_QSortFast(5, aQSort_i32, _)
#longuse ALongdef_QSortFast(6, aQSort_i32, _)
#longuse ALongdef_QSortFast(7, aQSort_i32, _)
#longuse ALongdef_QSortFast(4, aQSort_i64, _)
#longuse ALongdef_QSortFast(5, aQSort_i64, _)
#longuse ALongdef_QSortFast(6, aQSort_i64, _)
#longuse ALongdef_QSortFast(7, aQSort_i64, _)
#longuse ALongdef_QSortFast(12, aQSort_sub, _)
#longuse ALongdef_QSortFast(13, aQSort_sub, _)
#longuse ALongdef_QSortFast(14, aQSort_sub, _)
#longuse ALongdef_QSortFast(15, aQSort_sub, _)
AStatic void aQSort12(void *bas, AInt n, AInt sz, int (*cmp)(const void *, const void *))
// これが<stdlib.h>のqsort()相当.
{
if (sz == sizeof (aQSort_i64)) { aQSort(4, aQSort_i64)(bas, n, cmp); }
else if (sz == sizeof (aQSort_i32)) { aQSort(4, aQSort_i32)(bas, n, cmp); }
else { aQSort(12, aQSort_sub)(bas, n, sz, cmp); }
}
AStatic void aQSort13(void *bas, AInt n, AInt sz, void *a0, void *a1, int (*cmp)(const void *, const void *))
{
if (sz == sizeof (aQSort_i64)) { aQSort(5, aQSort_i64)(bas, n, a0, a1, cmp); }
else if (sz == sizeof (aQSort_i32)) { aQSort(5, aQSort_i32)(bas, n, a0, a1, cmp); }
else { aQSort(13, aQSort_sub)(bas, n, sz, a0, a1, cmp); }
}
AStatic void aQSort14(void *bas, AInt n, AInt sz, int (*cmp)(const void *, const void *, void *), void *w)
{
if (sz == sizeof (aQSort_i64)) { aQSort(6, aQSort_i64)(bas, n, cmp, w); }
else if (sz == sizeof (aQSort_i32)) { aQSort(6, aQSort_i32)(bas, n, cmp, w); }
else { aQSort(14, aQSort_sub)(bas, n, sz, cmp, w); }
}
AStatic void aQSort15(void *bas, AInt n, AInt sz, void *a0, void *a1, int (*cmp)(const void *, const void *, void *), void *w)
{
if (sz == sizeof (aQSort_i64)) { aQSort(7, aQSort_i64)(bas, n, a0, a1, cmp, w); }
else if (sz == sizeof (aQSort_i32)) { aQSort(7, aQSort_i32)(bas, n, a0, a1, cmp, w); }
else { aQSort(15, aQSort_sub)(bas, n, sz, a0, a1, cmp, w); }
}
-ひとつのコードで12通りの引数タイプ、さらにそれぞれ高速化とコード量のバランスを制御するための組み合わせが4通りあるので、コードが複雑になっています。
Mod=0 void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n)
Mod=1 void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n, Typ *a0, Typ *a1)
Mod=2 void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n, void *w)
Mod=3 void aQSortFast(Mod, Typ, CmpFnc)(Typ *bas, AInt n, Typ *a0, Typ *a1, void *w)
Mod=4 void aQSort(Mod, Typ)(Typ *bas, AInt n, int (*cmp)(const void *, const void *))
Mod=5 void aQSort(Mod, Typ)(Typ *bas, AInt n, Typ *a0, Typ *a1, int (*cmp)(const void *, const void *))
Mod=6 void aQSort(Mod, Typ)(Typ *bas, AInt n, int (*cmp)(const void *, const void *, void *), void *w)
Mod=7 void aQSort(Mod, Typ)(Typ *bas, AInt n, Typ *a0, Typ *a1, int (*cmp)(const void *, const void *, void *), void *w)
Mod=12 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz, int (*cmp)(const void *, const void *))
Mod=13 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz, void *a0, void *a1, int (*cmp)(const void *, const void *))
Mod=14 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz, int (*cmp)(const void *, const void *, void *), void *w)
Mod=15 void aQSort(Mod, Typ)(void *bas, AInt n, AInt sz, void *a0, void *a1, int (*cmp)(const void *, const void *, void *), void *w)
--Mod=12の形式がqsort()互換です。
//-本当は #longdef @ALongdef_QSortFast(@Mod, @Typ, @CmpFnc) とすべきだし、Modも(@Mod)として式を書かれても平気なようにするべきなのですが、面倒なのでまだやっていません・・・。
** (2) サンプルコード#1
-intの配列を100万用意して、ソートします。コンパイラの最適化能力が優秀なら、標準関数のqsortよりもかなり高速になります（比較関数がインライン展開されるためです）。
#include "acl1Tiny.c"
#include_once "once_aQSort.c"
uint32_t aXorShift32_i = 2463534242U;
AStatic uint32_t aXorShift32()
{
uint32_t i = aXorShift32_i;
i = i ^ (i << 13);
i = i ^ (i >> 17);
i = i ^ (i << 5);
aXorShift32_i = i;
return i;
}
AInlineStatic int cmpInt(const void *a, const void *b) { return *(int *)a - *(int *)b; }
#longuse ALongdef_QSortFast(0, int, cmpInt)
int main()
{
int i, n = 1000000, *a = malloc(n * sizeof (int));
for (i = 0; i < n; i++)
a[i] = aXorShift32() % 100000; // 10万.
aQSortFast(0, int, cmpInt)(a, n); // とりあえず全部ソート.
for (i = 0; i < 100; i++)
printf("%d ", a[i]);
return 0;
}
~
-別バージョン。この書き方でも同じ結果になります。速度は格段に速くなります。
-これは手抜きで最初の100件だけをソートしてるわけではなく、ちゃんと100万件の中から必要な100件を探してきています。残りは不揃いになっています（その不要部分のソートをしない分だけ高速になったと言うわけです）。
-これは手抜きで最初の100件だけをソートしてるわけではなく、ちゃんと100万件の中から必要な100件を探してきています。でも残りは不揃いになっています（この非表示部分のソートをしない分だけ高速になったと言うわけです）。
-最初のN件だけではなく、真ん中の一つだけ（メジアン）みたいな指定もできます。
（前略）
#longuse ALongdef_QSortFast(1, int, cmpInt)
（中略）
aQSortFast(1, int, cmpInt)(a, n, &a[0], &a[100]); // a[0～99]だけを正確にソート.
（後略）
** (3) サンプルコード#2
-もうちょっと複雑な例を用意してみます。
（前略）
AClass(Data) { int key[4]; };
AInlineStatic int cmpKey20(const void *a, const void *b)
{
if ((*(Data **)a)->key[2] > (*(Data **)b)->key[2]) return +1;
if ((*(Data **)a)->key[2] < (*(Data **)b)->key[2]) return -1;
if ((*(Data **)a)->key[0] > (*(Data **)b)->key[0]) return +1;
if ((*(Data **)a)->key[0] < (*(Data **)b)->key[0]) return -1;
return 0;
}
#longuse ALongdef_QSortFast(0, Data *, cmpKey20)
int main()
{
int i, j, n = 1000000;
Data *a = malloc(n * sizeof (Data)), **p = malloc(n * sizeof (Data *));
for (i = 0; i < n; i++) {
for (j = 0; j < 4; j++)
a[i].key[j] = aXorShift32() % 1000; // 1千.
p[i] = &a[i];
}
aQSortFast(0, Data *, cmpKey20)(p, n); // とりあえず全部ソート.
for (i = 0; i < 10; i++)
printf("(%d,%d,%d,%d)\n", p[i]->key[0], p[i]->key[1], p[i]->key[2], p[i]->key[3]);
return 0;
}
-これは、4つのデータをもつ構造体をソートしています。ソート速度を上げるために、a[]をそのままソートするのではなく、ポインタの配列p[]をソートしています（非常に一般的な手法です）。
-このプログラムでは、ソートにあたって、まず第一キーとしてkey[2]を使い、第二キーとしてkey[0]を使っています。第一キーが等しいとき、第二キーで大小を判定します。
-これはこれでいいのですが、第一キーと第二キーって、変数で指定したいと思いませんか？変数で指定できないと、すべての組み合わせを可能にするには、4x3=12の関数を作らなければいけなくなってしまいます。
~
-それをやるには、比較関数に追加の引数を渡す必要が出てきます。そのためにMod=2,3,6,7,14,15があります。
（前略）
AInlineStatic int cmpKeyExtPrm(const void *a, const void *b, void *w)
// 追加の引数は1つしかないので（w）、配列もしくは構造体のポインタを渡す.
{
int *extParam = (int *) w, i = extParam[0], j = extParam[1];
if ((*(Data **)a)->key[i] > (*(Data **)b)->key[i]) return +1;
if ((*(Data **)a)->key[i] < (*(Data **)b)->key[i]) return -1;
if ((*(Data **)a)->key[j] > (*(Data **)b)->key[j]) return +1;
if ((*(Data **)a)->key[j] < (*(Data **)b)->key[j]) return -1;
return 0;
}
#longuse ALongdef_QSortFast(2, Data *, cmpKeyExtPrm)
int main()
{
int i, j, n = 1000000;
Data *a = malloc(n * sizeof (Data)), **p = malloc(n * sizeof (Data *));
for (i = 0; i < n; i++) {
for (j = 0; j < 4; j++)
a[i].key[j] = aXorShift32() % 1000; // 1千.
p[i] = &a[i];
}
static int extParam[] = { 2, 0 }; // 今回の追加の引数.
aQSortFast(2, Data *, cmpKeyExtPrm)(p, n, extParam); // とりあえず全部ソート.
for (i = 0; i < 10; i++)
printf("(%d,%d,%d,%d)\n", p[i]->key[0], p[i]->key[1], p[i]->key[2], p[i]->key[3]);
return 0;
}
** (4) ベンチマーク
-(4-1) 前提：
// 乱数で初期配列を準備(a).
aXorShift32_seed(0); // seedをデフォルトに固定.
for (i = 0; i < n; i++)
a[i] = aXorShift32() % 1000;
// 逆順になるように初期配列を用意(b).
for (i = 0; i < n; i++)
a[i] = n - i;
-(4-2) (a)で初期化してソートする場合（n=100万）
|#0|qsort(a, n, sizeof (int), cmpInt);|0.112秒|（比較の基準として）|
|#1|aQSortFast(0, int, cmpInt)(a, n);|0.057秒|#0の1.96倍速|
|#2|aQSortFast(1, int, cmpInt)(a, n, &a[n / 2 - 1], &a[n / 2]);|0.010秒|メジアンのみ計算、#1の5.7倍速|
|#3|aQSort12(a, n, sizeof (int), cmpInt);|0.112秒|qsort互換、速度は#0と同じ|
-(4-3) (b)で初期化してソートする場合（n=100万）
|#4|qsort(a, n, sizeof (int), cmpInt);|0.124秒|qsortは逆順にそろった状態が少し苦手らしい|
|#5|aQSortFast(0, int, cmpInt)(a, n);|0.023秒|aQSortなら逆順はむしろ速くなる、#4の5.39倍速|
|#6|aQSort12(a, n, sizeof (int), cmpInt);|0.071秒|qsort互換、速度は#4の1.75倍速|
~
-(4-4) 次の前提：
typedef struct Data_ { int key[4]; } Data;
inline static int cmpKey20(const void *a, const void *b) // 今回の比較関数.
{
if ((*(Data **)a)->key[2] > (*(Data **)b)->key[2]) return +1;
if ((*(Data **)a)->key[2] < (*(Data **)b)->key[2]) return -1;
if ((*(Data **)a)->key[0] > (*(Data **)b)->key[0]) return +1;
if ((*(Data **)a)->key[0] < (*(Data **)b)->key[0]) return -1;
return 0;
}
// 乱数で初期配列を準備(c)
aXorShift32_seed(0); // seedをデフォルトに固定.
for (i = 0; i < n; i++) {
for (j = 0; j < 4; j++)
d[i].key[j] = aXorShift32() % 1000;
a[i] = &d[i];
}
-(4-5) (c)で初期化してソートする場合（n=100万）
|#7|qsort(a, n, sizeof (Data *), cmpKey20);|0.586秒||
|#8|aQSortFast(0, n, cmpKey20)(a, n);|0.332秒|#7の1.76倍速|
-(4-6) 比較関数に追加のパラメータを渡したい（ソートの軸の順番を変数で指定したい）
inline static int cmpKeyIj(const void *a, const void *b, void *extParam)
{
int i = ((int *) extParam)[0], j = ((int *) extParam)[1];
if ((*(Data **)a)->key[i] > (*(Data **)b)->key[i]) return +1;
if ((*(Data **)a)->key[i] < (*(Data **)b)->key[i]) return -1;
if ((*(Data **)a)->key[j] > (*(Data **)b)->key[j]) return +1;
if ((*(Data **)a)->key[j] < (*(Data **)b)->key[j]) return -1;
return 0;
}
-(4-7) (c)で初期化してソートする場合（n=100万）
|#9|static int extParam[] = { 2, 0 }; aQSortFast(2, n, cmpKeyIj)(a, n, extParam);|0.329秒|なぜ#8よりもわずかに速いのかは分からない|
-(4-8) まとめ
|#0|qsort(a, n, sizeof (int), cmpInt);|0.112秒|（比較の基準として）|
|#1|aQSortFast(0, int, cmpInt)(a, n);|0.057秒|#0の1.96倍速|
|#2|aQSortFast(1, int, cmpInt)(a, n, &a[n / 2 - 1], &a[n / 2]);|0.010秒|メジアンのみ計算、#1の5.7倍速|
|#3|aQSort12(a, n, sizeof (int), cmpInt);|0.112秒|qsort互換、速度は#0と同じ|
|#4|qsort(a, n, sizeof (int), cmpInt);|0.124秒|qsortは逆順にそろった状態が少し苦手らしい|
|#5|aQSortFast(0, int, cmpInt)(a, n);|0.023秒|aQSortなら逆順はむしろ速くなる、#4の5.39倍速|
|#6|aQSort12(a, n, sizeof (int), cmpInt);|0.071秒|qsort互換、速度は#4の1.75倍速|
|#7|qsort(a, n, sizeof (Data *), cmpKey20);|0.586秒||
|#8|aQSortFast(0, n, cmpKey20)(a, n);|0.332秒|#7の1.76倍速|
|#9|static int extParam[] = { 2, 0 }; aQSortFast(2, n, cmpKeyIj)(a, n, extParam);|0.329秒|なぜ#8よりもわずかに速いのかは分からない|
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
