#include <stdio.h>
int a[100000]={};
void s(int l, int r)
{
int t=a[l];
a[l]=a[r];
a[r]=t;
}
int p(int b, int e)
{
int pivot=(b+e)/2;
int l=b;
int r=e;
while(l<r)
{
while(a[l]>a[pivot]&&l<r) l++;
while(a[r]<a[pivot]&&l<r) r--;
if(l<r){
s(l,r);
if(l==pivot) pivot=r;
}
}
s(pivot,r);
return r;
}
void q(int l, int r)
{
if(l<r)
{
q(l, p-1);
q(p+1, r);
}
}
void main()
{
int i, n;
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &a[i]);
}
q(0, n-1);
}
**************************
#include <stdio.h>
int a[1000]={};
//5
//1
//4
//5
//8
//2
void s(int l, int r)
{
int t=a[l];
a[l]=a[r];
a[r]=t;
}
int p(int b, int e)
{
int pivot=(b+e)/2;
int l=b;
int r=e;
while(l<r)
{
while(a[l]>a[pivot]&&l<r) l++;
while(a[r]<a[pivot]&&l<r) r--;
if(l<r){
s(l,r);
if(l==pivot) pivot=r;
}
}
s(pivot,r);
return r;
}
void q(int l, int r)
{
int piv;
if(l<r)
{
piv=p(l,r);
q(l, piv-1);
q(piv+1, r);
}
}
void main()
{
int i, n;
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &a[i]);
}
q(0, n-1);
for(i=0; i<n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
****************************
#include <stdio.h>
int a[1000]={};
void s(int l, int r)
{
int temp=a[l];
a[l]=a[r];
a[r]=temp;
}
int p(int l, int r)
{
int piv;
if(a[l]>a[piv])
{
s(l, r);
l++;
}
if(a[r]<a[piv])
{
s(l, r);
r--;
}
if(l==r)
{
piv=r;
}
return ;
}
void q(int l, int r)
{
if(l<r)
{
int piv=p(l, r);
q(l, piv-1);
q(piv+1, r);
}
}
void main()
{
int n, i;
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &a[i]);
}
q(0, n-1);
for(i=0; i<n; i++)
{
printf("%d ", a[i]);
}
}