クロスソート

クロスソート
Time Limit:1000 MS Memory limit:32768 K
テーマの説明
N個の数を入力して、すべての奇数の位置の数を小さいから大きいまで並べ替えて、偶数の位置の数を大きいから小さいまで並べ替えます.
入力
入力の最初の行は正の整数Nです.二番目の行はN個のマス目で区切られた整数です.
出力
出力は1行のN個だけで、要求に従って並べ替えられたシーケンスです.スペースで区切られます.
例の入力

6
1 2 3 4 5 6

サンプル出力

1 6 3 4 5 2

ヒント
 
ソース
2011ソフト1-5班『プログラム設計基礎』機試tongjiantao
サンプルプログラム

#include
#include
#include
#define num 1003
int a[num],b[num];
void qsort1(int a[],int l,int r)
{
    int key = a[l],i = l,j = r;
    if(l >= r) return ;
    while(i < j)
    {
        while(i < j && a[j] >= key)
            j--;
        a[i] = a[j];
        while(i < j && a[i] <= key)
            i++;
        a[j] = a[i];
    }
    a[i] = key;
    qsort1(a,l,i-1);
    qsort1(a,i+1,r);
}
void qsort2(int a[],int l,int r)
{
    int key = a[l],i = l,j = r;
    if(l >= r) return ;
    while(i < j)
    {
        while(i < j && a[j] <= key)
            j--;
        a[i] = a[j];
        while(i < j && a[i] >= key)
            i++;
        a[j] = a[i];
    }
    a[i] = key;
    qsort2(a,l,i-1);
    qsort2(a,i+1,r);
}
int main()
{
    int n;
    int x;
    scanf("%d",&n);
    int j = 0,k = 0;
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&x);
        if(i % 2 != 0)
            a[j++] = x;
        else
            b[k++] = x;
    }
    qsort1(a,0,j-1);
    qsort2(b,0,k-1);
    j = 0,k = 0;
    for(int i = 1;i <= n;i++)
    {
        if(i == 1)
           printf("%d",a[j++]);
        else
        {
            if(i%2 != 0)
            {
                printf(" %d",a[j++]);
            }
            else
            {
                printf(" %d",b[k++]);
            }
        }
    }
    printf("
");
    return 0;
}