C言語によるクイックソートの実装①(アルゴリズムの実装)

サンプルプログラム

ここでは実際に、C言語によるクイックソートの実装を見てみることにします。C言語でクイックソートを利用する方法は大きく分けて2通りあり、一つはアルゴリズム通りの実装を行う方法、そしてもう一つは、C言語の標準関数である、qsort関数を利用する方法です。ここでは、その両方を紹介します。

以下のプログラムを実行してみてください。

listex7-qsort-1 
#include <stdio.h>
#include <stdlib.h>

#define MAX_LENGTH	7	

void quick_sort(int*,int);
void quick_sort_part(int*,int,int);
void swap(int*,int,int);
void showData(int*,int);

void main(){
	int array[MAX_LENGTH] = { 4,2,5,6,1,9,3 };
	quick_sort(array,MAX_LENGTH);
}


//	クイックソート
void quick_sort(int* pArray,int size)
{
	quick_sort_part(pArray,0,size - 1);
}

//	部分クイックソート
void quick_sort_part(int* pArray,int left,int right){
	int i,j,pivot;
	// leftがright以上なら、処理終了
	if(left >= right){
		return;
	}
	pivot = pArray[left];	//	左端を軸に設定
	i = left;
	j = right;
	while(1){
		while(pArray[i] < pivot){
			i++;
		}
		while(pArray[j] > pivot){
			j--;
		}
		//	探索が終わったら、ループから抜ける
		if(i >= j){
			break;
		}    
		//	入れ替え処理
		swap(pArray,i,j);
	}
	//  配列の表示
    showData(pArray,MAX_LENGTH); 
	if (left < i - 1){
		//	基準値の左に 2 以上要素があれば左の配列を再帰的にソートする
		quick_sort_part(pArray, left, i - 1);
	}
	if (j + 1 <  right){
		// 基準値の右に 2 以上要素があれば右の配列を再帰的にソートする
		quick_sort_part(pArray, j + 1, right);
	}
}
//	値の入れ替え
void swap(int* pArray,int i,int j)
{
	int tmp = pArray[i];
	pArray[i] = pArray[j];
	pArray[j] = tmp;
}
//	配列の表示
void showData(int* array,int length){
	int i;
	for(i = 0; i < length; i++){
		printf("%d ",array[i]);
	}
	printf("\n");
}
実行結果
3 2 1 4 6 9 5
1 2 3 4 6 9 5
1 2 3 4 6 9 5
1 2 3 4 5 6 9

C言語によるクイックソートの実装②(qsort関数の利用)

qsort関数

C言語には、配列の並べ替えを高速に行うための関数があらかじめ備わっています。それが、qsort関数で、クイックソートを行う関数です。この関数を利用するためには、stdlib.hをインクルードする必要があります。関数の仕様は以下のようになります。

qsort関数
qsort(配列の先頭アドレス,配列の要素数,配列1要素のバイト数,比較関数)

比較関数は、1回分の比較処理を定めた関数です。二つの引数を比較し、その結果をintで返します。その引数を先頭から、n1,n2としたとき、戻り値は以下のように定義します。

降順でのソートは、不等号の向きを逆にすれば可能です。なお、この例は数値の場合です。文字列など、特殊なデータの場合は、独自にルールを策定し、関数内で定義します。

サンプルプログラム

では実際に、この関数を利用したプログラムを実行してみましょう。

listex7-qsort-2 
#include <stdio.h>
#include <stdlib.h>

#define MAX_LENGTH	7

int compare(const void*,const void*);
void showData(int*,int);

void main(){
    int array[MAX_LENGTH] = { 4,2,5,6,1,9,3 };
    qsort(array,MAX_LENGTH,sizeof(int),compare);
	showData(array,MAX_LENGTH);
}

//	比較関数の実装
int compare(const void* n1,const void* n2)
{
	int x = *((int*)n1);
	int y = *((int*)n2);
	if(x > y){
		return 1;
	}else if(x < y){
		return -1;
	}else{
		return 0;
	}
}
//  配列の表示
void showData(int* array,int length){
    int i;
    for(i = 0; i < length; i++){
        printf("%d ",array[i]);
    }
    printf("\n");
}
実行結果
1 2 3 4 5 6 9