■クイックソート


▼クイックソートのアルゴリズム





▼上記アルゴリズムをイメージして作成したプログラム

2013/12/16 Miku Hatsuneさんのご指摘により、重複値のあるデータをソートしようとすると無限ループになるようです。

#include <stdio.h>

void q_sort(int*ar,int start,int end){
	if(start>=end) return;
	int bibot=ar[start+(end-start)/2];

	int i=start;
	int j=end;
	while(i<j){
		if(ar[i]<bibot) i++;
		if(ar[j]>bibot){
			j--;
		}else if(!(ar[i]<bibot)){
			int pos=ar[j];
			ar[j]=ar[i];
			ar[i]=pos;
		}
	}
	q_sort(ar,start,i);
	q_sort(ar,j+1,end);
}

int main(){

	int ar[]={3,0,6,8,4,9,1,5,7,2};
	int ar_size=sizeof(ar)/sizeof(int)-1;

	q_sort(ar,0,ar_size);

	for(int i=0;i<=ar_size;i++){
		printf("%d ",ar[i]);
	}
	printf("\n");
	return 0;
}




▼実行結果

0 1 2 3 4 5 6 7 8 9




■標準ライブラリを使ってクイックソート

クイックソートはstdlib.hに宣言されており、宣言されたqsortを使うと次のようになります

#include <stdio.h>
#include <stdlib.h>

int compar(const void *a, const void *b)
{
//小さい、等しい、大きいのそれぞれに応じて、
//マイナス値、ゼロ、プラス値 を返す必要がある
//昇順    return *(int *)a - *(int *)b;
//降順    return -(*(int *)a) + *(int *)b;
	return *(int *)a - *(int *)b;
}

int main(){

	int ar[]={3,0,6,8,4,9,1,5,7,2};
	int ar_size=sizeof(ar)/sizeof(ar[0]);

	qsort(ar, ar_size, sizeof(ar[0]),compar);

	for(int i=0;i<ar_size;i++){
		printf("%d ",ar[i]);
	}
	printf("\n");
	return 0;
}


▼実行結果

0 1 2 3 4 5 6 7 8 9




■標準ライブラリを使って文字列のクイックソート
比較関数にstrcmpを使うことにより文字列もソートできます

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compar(const void *a, const void *b)
{
	return strcmp(*(const char**)a,*(const char**)b);
}

int main(){

	char*ar[]={"abc","aaaa","aaa","aa","a","ab","b","bb","bbb","bbbb"};
	int ar_size=sizeof(ar)/sizeof(ar[0]);

	qsort(ar, ar_size, sizeof(ar[0]),compar);

	for(int i=0;i<ar_size;i++){
		printf("%s ",ar[i]);
	}
	printf("\n");
	return 0;
}

▼実行結果

a aa aaa aaaa ab abc b bb bbb bbbb




■標準ライブラリを使って構造体のクイックソート
構造体の中の変数を使ってソートします


#include <stdio.h>
#include <stdlib.h>

struct cell{
	int i;
	char str[20];
};

int compar(const void *a, const void *b)
{
	return (*(const cell*)a).i-(*(const cell*)b).i;
}

int main(){

	cell ar[]={
		4,"4です",
		3,"3です",
		2,"2です",
		1,"1です",
		0,"0です",
		9,"9です",
		8,"8です",
		7,"7です",
		6,"6です",
		5,"5です"};

	int ar_size=sizeof(ar)/sizeof(ar[0]);

	qsort(ar, ar_size, sizeof(ar[0]),compar);

	for(int i=0;i<ar_size;i++){
		printf("%d %s\n",ar[i].i,ar[i].str );
	}
	printf("\n");
	return 0;
}

▼実行結果

0 0です
1 1です
2 2です
3 3です
4 4です
5 5です
6 6です
7 7です
8 8です
9 9です






▲トップページ > プログラミングの実験