アルゴリズムクイックリファレンス 第2版

78

■

4

章 整列アルゴリズム

n

−

1

個の要素の

2

つの集まりに分割されている（ピボット要素が元の

n

個の最後の

要素になっているので、要素を失っているわけではない）。

4.4.2

 解

例4-6に示す

クイックソート

の実装は、整列する部分配列のサイズが前もって定め

た最小サイズに達すると

挿入ソート

を用いるという標準的な最適化を含む。

例

4-6

 

C

によるクイックソート実装

/**

*

クイックソートによる配列の整列。要素比較には、比較関数

cmp

が必要。

*/

void do_qsort (void **ar, int(*cmp)(const void *,const void *),

int left, int right) {

int pivotIndex;

if (right <= left) { return; }

/*

分割

*/

pivotIndex = selectPivotIndex (ar,

left, right);

pivotIndex = partition (ar, cmp, left, right, pivotIndex);

if (pivotIndex-1-left <= minSize) {

insertion (ar, cmp, left, pivotIndex-1);

} else {

do_qsort (ar, cmp, left, pivotIndex-1);

}

if (right-pivotIndex-1 <= minSize) {

insertion ...