#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;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHRpbWUuaD4KI2RlZmluZSBNQVggMTAwCiNkZWZpbmUgUkFOR0UgMTAwMAogCi8qIOygleugrOydhCDsiJjtlontlZjripQg67aA67aEKi8Kdm9pZCBRdWlja1NvcnQoaW50IFN0YXJ0LCBpbnQgTGFzdCwgaW50ICpBcnIpewoJaW50IEw9U3RhcnQ7CglpbnQgUj1MYXN0OwoJaW50IHRlbXA9MDsKCWludCBwaXZvdD0oQXJyW1N0YXJ0XStBcnJbTGFzdF0rQXJyWyhTdGFydCtMYXN0KS8yXSkvMzsKCXdoaWxlKDEpewoJCXdoaWxlKEFycltMXTxwaXZvdCkgTCsrOwoJCXdoaWxlKEFycltSXT5waXZvdCkgUi0tOwoJCWlmKEw8Uil7CgkJCXRlbXAgPSBBcnJbTF07CgkJCUFycltMXSA9IEFycltSXTsKCQkJQXJyW1JdID0gdGVtcDsKCQl9CgkJZWxzZSBicmVhazsKCX0KCQoJaWYoKEwtMSk+U3RhcnQpIFF1aWNrU29ydChTdGFydCxMLTEsQXJyKTsKCWlmKChSKzEpPkxhc3QpIFF1aWNrU29ydChSKzEsTGFzdCxBcnIpOwp9CiAKLyogMX5SQU5HReydmCDrspTsnITrpbwg6rCW64qUIOqyuey5mOyngCDslYrripQgTUFY6rCc7J2YIOyWkeyImOulvCDsg53shLHtlZjripQg67aA67aEICovCnZvaWQgTWFrZUFycihpbnQgKkFycil7CglpbnQgaSxrLHI7CglpbnQgcmFuW1JBTkdFXSA9ezAsfTsKCXNyYW5kKChpbnQpdGltZShOVUxMKSk7Cglmb3IoaT0wO2k8TUFYO2krKyl7CgkJciA9IHJhbmQoKSUoUkFOR0UtMSkrMTsKCQlpZighcmFuW3JdKXsKCQkJQXJyW2ldPXI7CgkJCXJhbltyXT0xOwoJCX0KCQllbHNlIGktLTsKCX0KfQogCi8qIOuwsOyXtOydmCDstpzroKUuIOyGjO2MheydtCDsmYTrsr3tlZzsp4Ag6rKA7IKs7ZW067O464ukLiAqLwp2b2lkIFByaW50QXJyKGludCAqQXJyKXsKCWludCBpPTA7Cglmb3IoaT0wO2k8TUFYLTE7aSsrKXsKCQlpZihBcnJbaV0+QXJyW2krMV0pIGJyZWFrOzsKCX0KCWlmKGk9PU1BWClwcmludGYoInBlcmZlY3RseSBzb3J0ZWRcbiIpOwoJZWxzZSBwcmludGYoIm5vdCBwZXJmZWN0XG5BcnJbJWRdPSVkLEFyclslZF09JWQgXG4iLGksQXJyW2ldLGkrMSxBcnJbaSsxXSk7Cglmb3IoaT0wO2k8TUFYO2krKyl7CgkJcHJpbnRmKCIlZCAiLEFycltpXSk7Cgl9Cn0KIAppbnQgbWFpbih2b2lkKSB7CglpbnQgQXJyW01BWF07CglpbnQgaTsKCWludCBsZW5ndGg7CiAKCWlmKFJBTkdFPE1BWCl7CgkJcHJpbnRmKCJSQU5HRSBtdXN0IGJlIGxhcmdlciB0aGFuIE1BWCIpOwoJCXJldHVybiAtMTsKCX0KIAoJTWFrZUFycihBcnIpOwoJZm9yKGk9MDtpPE1BWDtpKyspewoJCXByaW50ZigiJWQgIixBcnJbaV0pOwoJfQoJcHJpbnRmKCJcbiIpOwoJbGVuZ3RoID0gc2l6ZW9mKEFycikvc2l6ZW9mKGludCk7CglRdWlja1NvcnQoMCxsZW5ndGgtMSxBcnIpOwoJUHJpbnRBcnIoQXJyKTsKCXJldHVybiAwOwp9CiA=