C言語でのクイックソートの実装法の解説。
クイックソート (quicksort) とは、ソートアルゴリズムの一種である。その名の通り非常に高速なソートアルゴリズムであり、一般的には現在発見されているソートアルゴリズムの中で最速のアルゴリズムであると言われているが、データの順序や数によっては必ずしも速いわけではない。平均時間計算量は で最悪時間計算量は である。安定ソート (stable sort) ではない。
クイックソートでは、集合全体をとある値を基準にそれより前に来る物と後に来る物に分割し、それぞれを同様に再帰的に分割していく事によって全体をソートするアルゴリズムである。
また、このように、大きな問題を小さな幾つかの問題に分割し、それぞれを解決する事によって問題全体を解決する方法を分割統治法 (divide and conquer algorithm) という。
数値の集合を昇順にソートする方法を例に取り、クイックソートの実装法について解説する。また、これは実装方法の一つであり、一部分のアルゴリズムを別のアルゴリズムで代用する事も可能である。
以下のような配列があるとする。
int array[8] = {6,2,9,4,6,1,3,7};
この配列を、とある値を基準にその値未満の物とその値以上の物に分割する事を考える。
先ず、基準となる値を選ぶ必要がある。基準値は配列の中央値である方が好ましい。また、配列の中で最も小さい値であってはならない。もし配列内で最も小さい値が選ばれてしまうと、配列内の全ての値が基準値以上になり、再帰的な無限ループに陥る可能性がある。実装例を以下に示す。(select_pivot.c)
1
2 #include <stdio.h>
3
4 size_t select_pivot(int *array,size_t size)
5 {
6 size_t counter = 1;
7 while(counter != size && array[counter-1] == array[counter]){
8 counter++;
9 }
10 return counter == size || array[counter-1] < array[counter]?counter
11 :counter-1;
12 }
13
14 int main(void)
15 {
16 int array[8] = {6,6,1,4,2,9,3,7};
17 size_t pivot = select_pivot(array,8);
18 if(pivot != 8){
19 printf("pivot : array[%d] = %d\n",pivot,array[pivot]);
20 }
21 else{
22 printf("sorted\n");
23 }
24 return 0;
25 }
これを実行すると以下のような出力が得られる。
pivot : array[1] = 6
また、もし16行目の配列 array を {3,3,3,3,3,3,3,3} のように全て同じ値にすると、 sorted と出力される。
この例では、4行目の select_pivot() 関数が基準値を選ぶ役割を持っている。この関数は、与えられた配列を先頭から走査し、隣り合う2つの値が違う箇所を発見すればそのうちの大きい方の位置を返し、全ての値が同じであれば配列のサイズを返すようになっている。上で述べた通り、この基準値は配列の中で最も小さい値であってはならないが、この方法ではかならず配列の別の値より大きい値になっている。
次に、この値を基準に配列を2つに分ける方法について考える。
実装方法としては、配列を先頭と末尾から中心に向かって探索し、先頭から探索して最初に見付かった基準値以上の値と、末尾から探索して最初に見付かった基準値未満の値を取り替える操作を繰り返すのが一般的である。実装例を以下に示す。(partition.c)
1
2 #include <stdio.h>
3
4 static size_t select_pivot(int *array,size_t size)
5 {
6 size_t counter = 1;
7 while(counter != size && array[counter-1] == array[counter]){
8 counter++;
9 }
10 return counter == size || array[counter-1] < array[counter]?counter
11 :counter-1;
12 }
13
14 size_t partition(int *array,size_t size)
15 {
16 size_t pivot_pos = select_pivot(array,size)
17 ,first_to_last = 0,last_to_first = size-1;
18 int pivot,temp;
19 if(pivot_pos == size){
20 return 0;
21 }
22 pivot = array[pivot_pos];
23 while(first_to_last < last_to_first){
24 while(pivot > array[first_to_last] && first_to_last != size-1){
25 first_to_last++;
26 }
27 while(pivot <= array[last_to_first] && last_to_first){
28 last_to_first--;
29 }
30 if(first_to_last < last_to_first){
31 temp = array[first_to_last];
32 array[first_to_last] = array[last_to_first];
33 array[last_to_first] = temp;
34 }
35 }
36 return first_to_last;
37 }
38
39 int main(void)
40 {
41 int array[8] = {6,6,1,4,2,9,3,7};
42 size_t partition_pos = partition(array,8),counter = 0;
43 if(!partition_pos){
44 printf("sorted\n");
45 }
46 else{
47 printf("part1 : ");
48 while(counter != partition_pos){
49 printf("%d ",array[counter]);
50 counter++;
51 }
52 printf("\npart2 : ");
53 while(counter != 8){
54 printf("%d ",array[counter]);
55 counter++;
56 }
57 printf("\n");
58 }
59 return 0;
60 }これを実行すると以下のような出力が得られる。
part1 : 3 2 1 4 part2 : 6 9 6 7
この例では、14行目の partition() 関数が配列の分割を行う役割を持っている。これは以下の様な手順で配列の分割を実現している。
上の例で行われている操作を図で表すと以下のようになる。
基準値は6なので、このように配列全体が6未満の値と6以上の値に分割されている。
次に、再帰的に分割を繰り返し、全体をソートする事を考える。
配列の中身が全て同じであった場合に分割は出来ず、また既にソート済みであると考える事もできるため、そのような場合に再帰しないような実装にすれば良い。実装例を以下に示す。(quicksort.c)
1
2 #include <stdio.h>
3
4 static size_t select_pivot(int *array,size_t size)
5 {
6 size_t counter = 1;
7 while(counter != size && array[counter-1] == array[counter]){
8 counter++;
9 }
10 return counter == size || array[counter-1] < array[counter]?counter
11 :counter-1;
12 }
13
14 static size_t partition(int *array,size_t size)
15 {
16 size_t pivot_pos = select_pivot(array,size)
17 ,first_to_last = 0,last_to_first = size-1;
18 int pivot,temp;
19 if(pivot_pos == size){
20 return 0;
21 }
22 pivot = array[pivot_pos];
23 while(first_to_last < last_to_first){
24 while(pivot > array[first_to_last] && first_to_last != size-1){
25 first_to_last++;
26 }
27 while(pivot <= array[last_to_first] && last_to_first){
28 last_to_first--;
29 }
30 if(first_to_last < last_to_first){
31 temp = array[first_to_last];
32 array[first_to_last] = array[last_to_first];
33 array[last_to_first] = temp;
34 }
35 }
36 return first_to_last;
37 }
38
39 void quicksort(int *array,size_t size)
40 {
41 size_t partition_pos = partition(array,size);
42 if(partition_pos){
43 quicksort(array,partition_pos);
44 quicksort(&array[partition_pos],size-partition_pos);
45 }
46 }
47
48 int main(void)
49 {
50 int array[8] = {6,6,1,4,2,9,3,7};
51 size_t counter = 0;
52 quicksort(array,8);
53 while(counter != 8){
54 printf("%d ",array[counter]);
55 counter++;
56 }
57 return 0;
58 }これを実行すると以下のような出力が得られる。
1 2 3 4 6 6 7 9
この例では、39行目の quicksort() 関数が再帰による分割の繰り返しを行っている。42行目で partition_pos が0でない場合に再帰を行うようになっている。このように、クイックソートを使用すれば容易にソートアルゴリズムを実装出来る。
要素のサイズと比較の関数を与えるような仕様にする事によって、より汎用的なクイックソートを実装する事ができる。以下に実装例を示す。(general_purpose_quicksort.c)
1
2 #include <stdio.h>
3 #include <stdlib.h>
4
5 static void quicksort_(void *base,const size_t num,const size_t size
6 ,void *temp,int (*compare)(const void *,const void *))
7 {
8 size_t pivot = 0,first2last = 0,last2first = num-1;
9 while(pivot+1 != num && !compare(base+size*pivot,base+size*(pivot+1))){
10 pivot++;
11 }
12 if(pivot+1 == num){
13 return;
14 }
15 if(0 > compare(base+size*pivot,base+size*(pivot+1))){
16 pivot++;
17 }
18 while(first2last < last2first){
19 while(0 < compare(base+size*pivot,base+size*first2last)
20 && first2last != num-1){
21 first2last++;
22 }
23 while(0 >= compare(base+size*pivot,base+size*last2first)
24 && last2first){
25 last2first--;
26 }
27 if(first2last < last2first){
28 if(pivot == first2last || pivot == last2first){
29 pivot = pivot^last2first^first2last;
30 }
31 memcpy(temp,base+size*first2last,size);
32 memcpy(base+size*first2last,base+size*last2first,size);
33 memcpy(base+size*last2first,temp,size);
34 }
35 }
36 quicksort_(base,first2last,size,temp,compare);
37 quicksort_(base+size*first2last,num-first2last,size,temp,compare);
38 }
39
40 int quicksort(void *base,const size_t num,const size_t size
41 ,int (*compare)(const void *,const void *))
42 {
43 void *temp = malloc(size);
44 if(!temp){
45 return -1;
46 }
47 quicksort_(base,num,size,temp,compare);
48 free(temp);
49 return 0;
50 }
51
52 int compare_integer(const void *a,const void *b)
53 {
54 return *(int *)a-*(int *)b;
55 }
56
57 int main(void)
58 {
59 int array[8] = {6,6,1,4,2,9,3,7};
60 int errcode = quicksort(array,8,sizeof(int),compare_integer);
61 size_t counter = 0;
62 if(errcode < 0){
63 fputs("Error!\n",stderr);
64 return -1;
65 }
66 while(counter != 8){
67 printf("%d ",array[counter]);
68 counter++;
69 }
70 return 0;
71 }これを実行すると以下のような出力が得られる。ただし、メモリの動的確保に成功した場合に限る。
1 2 3 4 6 6 7 9
値の入れ替えに用いる変数のサイズが可変である必要があるため、関数を2つに分ける事によってメモリ領域の動的確保を最初1回だけ行うようにし、メモリ領域の動的確保の失敗のタイミングによってデータの破壊が起きないような実装にしている。また、配列の扱いが特殊になるため、複雑なポインタ演算や memcpy 関数を使用しているが、基本となるアルゴリズムは変わらない。
この例での40行目の quicksort() 関数は、C言語の標準ライブラリである qsort() 関数とほぼ同じ形式を持ち、同じ機能を提供する。実際にプログラムを書く上でクイックソートを使用する分には qsort() 関数を使用するのが普通である。
基準値の選択の実装例。
集合の分割の実装例。
クイックソートの実装例。
より汎用的なクイックソートの実装例。