#include <stdio.h>

void swap(int a, int b, int x[])
{
    int tmp;

    tmp = x[a];
    x[a] = x[b];
    x[b] = tmp;
}

void qsort(int left, int right, int x[])
{
    int pivot, pivot_value, p, i;

    if ( left < right ) {
        pivot = (left + right)/2;  // 最初はド真ん中
        pivot_value = x[pivot];    // ピボットの設定
        x[pivot] = x[left];        // ピボットを選んだ場所に一番左の要素を代入
        p = left;                  // p に一番左のインデックスを保存 

        for ( i = left + 1; i<= right; i++ ){
            if (x[i] < pivot_value ) { // x[i]がピボットより小さければ
                p++;                   // 値を入れるインデックスを計算し
                swap(p, i, x);         // x[p]とx[i]の値を交換
            }
        }
        x[left] = x[p];                // x[left]にx[p]を代入
        x[p] = pivot_value;            // ピボットの値を x[p]に代入
        // x[left]からx[p-1]はx[p]未満，x[p+1]からx[right]はx[p]以上となる

        qsort(left, p-1, x);
        qsort(p+1, right, x);
    }
}

int main(void)
{
    int x[]={3,1,2,6,5,4,7,9,8,0}, SIZE, i;

    SIZE = sizeof(x)/sizeof(x[0]);
    qsort(0, SIZE, x);
    for (i=0; i< SIZE; i++){
        printf("%d ", x[i]);
    }
    printf("\n");
    return 0;
}