配列中の要素の一番最初をピボットと名付ける 配列要素をピボットよりも小さいもの、ピボット、ピボットより大きいもの、に並び替える 配列要素の最初から、ピボットよりも小さいものを探す 配列要素の最後から、ピボットよりも大きいものを探す ピボットよりも小さいものが、ピボットよりも大きいものよりも後にあれば、ソート終了 そうでなければ、その２つの要素を交換する この処理を、その続きの範囲から繰り返す ピボットよりも左側と、右側の領域で、この処理を再帰的に行う。

　　このクイックソートは、今までに紹介した方法に比べて、処理速度が格段に速い。 JavaやMFCなどでは、標準関数として用意されている。

---

|　要素　|	ソート前　|	1回　|	2回　|	3回　|	4回　|	5回　|	6回　|	7回　|	8回　|	9回　|
0	84	51	43	14	14	14	14	14	14	14
1	121	14	14	43	43	43	43	43	43	43
2	43	43	51	51	51	51	51	51	51	51
3	93	83	83	83	83	83	83	83	83	83
4	140	140	140	140	140	84	84	84	84	84
5	83	93	93	93	93	93	93	93	93	93
6	14	121	121	121	121	121	121	121	93	93
7	93	93	93	93	93	93	93	93	121	121
8	181	181	181	181	181	181	181	181	181	140
9	51	84	84	84	84	140	140	140	140	181

#include <stdio.h> #define LEN 10 void display(int S[], int length); int *myQsort(int S[], int left, int right); /*----------------------- QuickSort クイックソート 軸要素は，左端(数列の先頭)でとってある． Copyright by ECB.------------------------*/ //--------メイン関数------------------ void main(){ int S[LEN] = {84,121,43,93,140,83,14, 93, 181, 51}; //配列の初期値 int *R; R = myQsort(S, 0, LEN-1); //クイックソート display(R, LEN); //結果表示 } //----------クイックソート-------------------- int *myQsort(int S[], int first, int last) { int i,j; int x; x = S[first]; //ピボット i = first; //first は 左境界，lastは 右境界 j = last; while(true) { //無限ループ int temp; while( S[i] < x ) i++; //交換する要素の決定 while( x < S[j] ) j--; if( i >= j ) break; //左境界が右境界を越えたら ループ終了 temp = S[i]; //S[i] と S[j]を交換 S[i] = S[j]; S[j] = temp; i++; //境界をさらにせばめる． j--; } display(S,LEN); //途中経過 if( first < i - 1 ) myQsort( S, first, i-1 ); //S[i], S[j]の変換があれば もう一度行なう． <- ポイント if( j + 1 < last ) myQsort( S, j+1, last ); return S; } //-------結果表示--------------- void display(int S[], int length){ for(int i = 0; i<length; i++) printf("%4d ",S[i]); printf("\n"); }