/*
#include <stdio.h>
int arr[50]={5,7,3,10,2,1};
int n=6;
void view(){
for(int i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
// quick_sort
void qs(int s, int e) // arr[s] ~ arr[e] 를 퀵정렬하세요
{
if(s>=e) return;
int pivot = s;
int left = s;
int right = e;
int temp;
while(1)
{
while(arr[pivot] >= arr[left])
{
left++;
}
while(arr[pivot] <= arr[right])
{
right--;
}
if(left>right)
break;
//arr[left]와 arr[right] 교환
temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;
}
//( arr[pivot] ) arr[pivot]보다 작은값들 arr[pivot]보다 큰 값들
temp=arr[pivot];
arr[pivot]=arr[right];
arr[right]=temp;
// arr[pivot]보다 작은값들 ( arr[pivot] ) arr[pivot]보다 큰 값들
qs(s,right-1);
qs(right+1,e);
}
int main()
{
view();
qs(0,n-1);
view();
return 0;
}
*/
/* quick sort 직접구현
#include<stdio.h>
int arr[100001]={};
void qs(int s, int e)
{
if(s>=e){
return;
}
int pivot=s;
int left=s;
int right=e+1;
int temp;
do{
do{
left++;
}while (arr[pivot]>arr[left]);
do{
right--;
}while (arr[pivot]<arr[right]);
if(right<left){
break;
}
temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;
}while(left<right);
temp=arr[pivot];
arr[pivot]=arr[right];
arr[right]=temp;
qs(s, right-1);
qs(right+1, e);
}
int main()
{
int n, i;
scanf ("%d", &n);
for(i=0; i<n; i++){
scanf("%d", &arr[i]);
}
qs(0, n-1);
for(i=0; i<n; i++){
printf("%d\n", arr[i]);
}
return 0;
}
*/
/*
//quick_sort 내장 함수 이용
#include<stdio.h>
#include<stdlib.h>
int arr[100001]={};
int compare(const int* a, const int* b)
{
if(*a<*b) return 1;
else if(*a>*b) return -1;
else return 0;
}
int main()
{
int n, i;
scanf ("%d", &n);
for(i=0; i<n; i++){
scanf("%d", &arr[i]);
}
//qsort(정렬 시작할 곳의 주소 , 몇 개 정렬할지, 정렬할 데이터의 크기, 기준 함수)
qsort(arr,n,sizeof(int),compare);
//&arr[0]
for(i=0; i<n; i++){
printf("%d\n", arr[i]);
}
return 0;
}
#include<stdio.h>
#include<stdlib.h>
int arr[100001]={};
int compare(const int* a, const int* b)
{
if(*a<*b){
return -1;
}
else if (*a>*b){
return 1;
}
else{
return 0;
}
}
int main()
{
int n, i;
scanf ("%d", &n);
for(i=0; i<n; i++){
scanf ("%d", &arr[i]);
}
qsort(arr, n, sizeof(int), compare);
for(i=0; i<n; i++){
printf ("%d\n", arr[i]);
}
return 0;
}*/
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int a;
int b;
}number;
number arr[50001]={}, temp;
void qs(int s, int e)
{
if(s>=e){
return;
}
int pivot=s;
int left=s;
int right=e+1;
do{
do{
left++;
}while(arr.a[pivot]>arr[left]);
do{
right--;
}while(arr[pivot]<arr[right]);
if(right<left){
break;
}
temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;
}
arr[pivot]=arr[right];
arr[right]=temp;
qs(s, right-1);
qs(right+1, e);
}
int main()
{
int n, i;
scanf("%d", &n);
for(i=0; i<n; i++){
scanf ("%d", &arr[i]);
arr[i].b=i;
}
qs()
for(i=0; i<n; i++){
}
}
/*
50 23 54 24 123
0 1 2 3 4
23 24 50 54 123//정렬
1 3 0 2 4
0 1 2 3 4
1 3 0 2 4
2 0 3 1 4
0 1 2 3 4//정렬
*/