#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 100
#define RANGE 1000
 
/* 정렬을 수행하는 부분*/
void QuickSort(int Start, int Last, int *Arr){
	int L=Start;
	int R=Last;
	int temp=0;
	int pivot=(Arr[Start]+Arr[Last]+Arr[(Start+Last)/2])/3;
	while(1){
		while(Arr[L]<pivot) L++;
		while(Arr[R]>pivot) R--;
		if(L<R){
			temp = Arr[L];
			Arr[L] = Arr[R];
			Arr[R] = temp;
		}
		else break;
	}
	
	if((L-1)>Start) QuickSort(Start,L-1,Arr);
	if((R+1)>Last) QuickSort(R+1,Last,Arr);
}
 
/* 1~RANGE의 범위를 갖는 겹치지 않는 MAX개의 양수를 생성하는 부분 */
void MakeArr(int *Arr){
	int i,k,r;
	int ran[RANGE] ={0,};
	srand((int)time(NULL));
	for(i=0;i<MAX;i++){
		r = rand()%(RANGE-1)+1;
		if(!ran[r]){
			Arr[i]=r;
			ran[r]=1;
		}
		else i--;
	}
}
 
/* 배열의 출력. 소팅이 완벽한지 검사해본다. */
void PrintArr(int *Arr){
	int i=0;
	for(i=0;i<MAX-1;i++){
		if(Arr[i]>Arr[i+1]) break;;
	}
	if(i==MAX)printf("perfectly sorted\n");
	else printf("not perfect\nArr[%d]=%d,Arr[%d]=%d \n",i,Arr[i],i+1,Arr[i+1]);
	for(i=0;i<MAX;i++){
		printf("%d ",Arr[i]);
	}
}
 
int main(void) {
	int Arr[MAX];
	int i;
	int length;
 
	if(RANGE<MAX){
		printf("RANGE must be larger than MAX");
		return -1;
	}
 
	MakeArr(Arr);
	for(i=0;i<MAX;i++){
		printf("%d ",Arr[i]);
	}
	printf("\n");
	length = sizeof(Arr)/sizeof(int);
	QuickSort(0,length-1,Arr);
	PrintArr(Arr);
	return 0;
}