// ■Quick Sort(C.A.Hoare) Example
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define DATALENGTH 10							// The number of Data
#define frand()((double)rand()/(RAND_MAX+1))	// Random number(0〜1)
#define swap(type,x,y) do{type t;t=x;x=y;y=t;}while(0)
int Data[DATALENGTH],sortData[DATALENGTH];
void initArray(){// Genaration of Sort Data(10 〜 99)
  for(int i=0;i<DATALENGTH;i++) Data[i]=(int)(frand()*89)+10;
}
void quickSort(int a[],int Left, int Right){
	int pL=Left, pR=Right, x = a[(pL + pR)/2];
	if((pR - pL)>5){// Section of Pivot Data
		int x1 = a[pL], x2 = a[pR];
		if     ((x<=x1 && x1<=x2)|| (x2<=x1 && x1<=x)) x=x1;
		else if((x<=x2 && x2<=x1)|| (x1<=x2 && x2<=x)) x=x2;
	}
	do{ // Scan
	  while(a[pL]<x) pL++; while(a[pR]>x) pR--;
	  if(pL<=pR){
		swap(int, a[pL],a[pR]); pL++; pR--;
	  }
	}while(pL<pR);
	if(Left < pR   ) quickSort(a, Left, pR   ); // Left Sort
	if(pL   < Right) quickSort(a, pL  , Right); // Right Sort
}
int main(){
	srand((unsigned int)(time(NULL)));// Random Number Initialize
	int i; 
	do{
	  initArray();
	  printf(" ソート前： %d",Data[0]);
	  for(i=1;i<DATALENGTH;i++) printf(", %d",Data[i]);
	  printf("\n");
	  quickSort(Data, 0, DATALENGTH-1);
	  printf(" ソート後： %d",Data[0]);
	  for(i=1;i<DATALENGTH;i++) printf(", %d",Data[i]);
	  printf("\n");
	} while(getchar()!=EOF);
}