/*#include <stdio.h>
int arr[1000001];
int bs(int s,int e,int k)
{
int mid=(s+e)/2;
if(s>e) return -1;
if(arr[mid]==k) return mid;
else if(arr[mid]>k) return bs(s,mid-1,k);
else if(arr[mid]<k) return bs(mid+1,e,k);
}
int main()
{
int e,s,n;
int k;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
}
printf("%d",bs(1,n,k));
return 0;
}*/
/*#include <stdio.h>
int main()
{
int j,k,i,n,arr[100001]={};
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
}
scanf("%d",&k);
for(j=1;j<=n;j++)
{
if(arr[j]==k)
{
printf("%d",j);
return 0;
}
}
printf("-1");
return 0;
}*/
/*#include <stdio.h>
int arr[1000001]={};
int bs(int s,int e,int k)
{
int mid=(s+e)/2;
if(s>e) return -1;
if(arr[mid]==k) return mid;
else if(arr[mid]>k) return bs(s,mid-1,k);
else if(arr[mid]<k) return bs(mid+1,e,k);
}
int main()
{
int e,s,k,a,n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
}
scanf("%d",&a);
for(i=1;i<=a;i++)
{
scanf("%d",&k);
printf("%d ",bs(1,n,k));
}
return 0;
}
느린애들 : 버블, 선택, 삽입
빠른애들 : "퀵정렬"
퀵정렬 : 기준값이 자기 자리를 찾아감!!
예를들면
5 7 3 10 2 1
->
3 1 2 "5" 7 10
quick sort -> qs
*/
#include <stdio.h>
int arr[1000001]={};
void qs(int s,int e) // arr[s] ~ arr[e] 를 퀵정렬해주세요
{
if(s>=e) return ; // 하나남았어? 그만해!
int pivot = s ; // 이번 라운드에서 자기 자리를 찾아갈 위치 ( 기준)
int left = s;
int right = e;
while(1)
{
while(arr[pivot] >= arr[left])
{
left++;
}
while(arr[pivot]<=arr[right])
{
right--;
}
if(right < left) break;
int tmp = arr[left];
arr[left]=arr[right];
arr[right]=tmp;
}
int tmp = arr[pivot];
arr[pivot]=arr[right];
arr[right]=tmp;
// ****arr[pivot]보다작은애들 **** arr[pivot] ****arr[pivot]보다큰애들*****
qs(s,right-1);
qs(right+1,e);
}
int main()
{
int e,s,k,a,n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
}
//퀵정렬
qs(1,n);
for(i=1;i<=n;i++)
{
printf("%d ",arr[i]);
}
return 0;
}