lab10 - なんだかいろいろウィキ

lab10

とりあえず教科書のクイックソートそのまま動くようにしました
名前のとおり早いですな

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

#define N 100005
void quicksort(int i,int j,int *A);
int partition(int i,int j,int a,int *A);
int pivot(int i,int j,int *A);
void swap(int i,int j,int *A);//配列A[i]とA[j]を入れ替える


int main(int argc,char *argv[])
{
 	FILE *fp;
  	fp = fopen("../rand50000.dat","r");
 	int A[N];
	int a,b,n=0,i,m,temp,j,k;
	fscanf(fp,"%d",&a);
 	for(i=0;i<a;i++){
 		fscanf(fp,"%d",&b);
 		A[i]=b;
 	}
 	printf("before:\n");
	for(i=0;i<a;i++)printf("%d ",A[i]);
	printf("\n\n\n\n");
	quicksort(0,a-1,A);
	printf("after:\n");
	for(i=0;i<a;i++)printf("%d ",A[i]);
	fclose(fp);
}
/*i=左端 j=右端 *A=整列したい配列*/
void quicksort(int i,int j,int *A){
	int a,pv,k;
	pv=pivot(i,j,A);
	if(pv!=-1){
		a=A[pv];
		k=partition(i,j,a,A);
		quicksort(i,k-1,A);
 		quicksort(k,j,A);
	}
	return;
}
/*i=左端 j=右端 a=??? *A=整列したい配列*/
int partition(int i,int j,int a,int *A){//分割した右端を返す
	int l,r,k;
	l=i;
	r=j;
	while(1){
		while(A[l]<a)l=l+1;
		while(A[r]>=a)r=r-1;
		if(l<=r){
			swap(l,r,A);
			l=l+1;
			r=r-1;
		}
		else break;
	}
		k=l;
		return k;
} 
/*i=左端 j=右端 *A=整列したい配列*/
int pivot(int i,int j,int *A){
 	int pv,k;
 	k=i+1;
	while(A[i]==A[k]&&k<=j) k=k+1;
 	if(k>j)pv=-1;
	else if(A[i]>=A[k])pv=i;
	else pv=k;
	return pv;
} 
void swap(int i,int j,int *A)//入れ替え
	{
		int temp;
		temp=A[i];A[i]=A[j];A[j]=temp;
		return;
 	}