quickSort  クイックソート

void quickSort(DATA *data, int nmem, int asdes);

typedef struct {
    int key;        /* 比較のキーとなるフィールド */
    int info;       /* その他のフィールド */
} DATA;

data   （入出力）データレコードの配列
nmem   （入力）　レコード配列の大きさ
asdes  （入力）　昇順・降順別、0:昇順, 1:降順

なし

void quickSort(DATA *data, int nmem, int asdes)
{
    static void rquickSort();

    if (nmem <= 1) return;
    rquickSort(data, asdes, 0, nmem - 1);
}

static void rquickSort(DATA *data, int asdes, int first, int last)
{
    int i, j, x;
    static void swap();

    i = first;
    j = last;
    x = (data[i].key + data[j].key)/2;
    while (i < j) {
        if (asdes == 0) {
            while (data[i].key < x) i++;
            while (data[j].key > x) j--;
        } else {
            while (data[i].key > x) i++;
            while (data[j].key < x) j--;
        }
        if (i < j) {
            swap(&data[i], &data[j]);
            i++;
            j--;
        }
    }
    if (first < i - 1) rquickSort(data, asdes, first, i - 1);
    if (last  > j + 1) rquickSort(data, asdes, j + 1, last);
}

static void swap(DATA *a, DATA *b)
{
    DATA t;

    t.key   = a->key;
    t.info  = a->info;
    a->key  = b->key;
    a->info = b->info;
    b->key  = t.key;
    b->info = t.info;
}

1. 適当な値 x を選ぶ。その際、配列の x 以下の要素の数と x 以上の 要素の数とはなるべく同程度になるようにする。
2. x 以下の要素を配列の前半に、x 以上の要素を配列の後半に集める。
3. 配列の前半が要素数が2以上なら、配列の前半を再帰的にクイック ソートする。
4. 配列の後半が要素数が2以上なら、配列の後半を再帰的にクイック ソートする。

利用するには、データ構造を実際の問題に合わせて修正する必要がある。