クイックソートをプログラムする

ここでは, クイックソートのアルゴリズムを C言語で書いて見ます. 実際にプログラムを書くには, 上のアルゴリズムをより具体的な形します. それは, 次です.

1. ピボットをどう選ぶか
2. ピボットを中心に配列を分割する方法をどう書くか.

ここでは手抜きをして, ピボットを配列の最初の元とします. 次のデータの分割方法ですが, 上に書いたようにピボットをデータの 端(右端でも左端でも良いが, ここでは左端)に置いて, 次の操作をします. 分割されるデータを a[0], $\cdots$, a[n] とします. ピボットは a[0]です.

1. 添字を動く変数 i と last を用意し, last を左端, iは左端を 1つ進んだ値 とおく.
2. i = 初期値から右端(今の場合 n)まで動かし次の操作をする.
   1. a[i] $\geqq$ a[0] なら何もしない.
   2. a[i] $<$ a[0] なら last を 1 増やし, a[i] と a[last] を入れ換る.
3. a[0] と a[last] を入れ換える.

上の方針で書いたのが次のプログラムです. クイックソートは その形から再帰的なプログラムになるので, quicksort と 言う名前の函数を用意します. 函数に配列を引数で渡しますが, この例の様に配列名で渡します. この詳しい仕組みを知りたい方は, 後期の 授業を受けるか, 自習するかして下さい.

/* File name 13-2.c */

#include <stdio.h>
#define SIZE 20

int data[SIZE]= {99,73,20,32,34,5,64,97,25,12,83,9,21,40,3,44,69,15,58,75};

void quicksort(int list[], int left, int right);

main()
{
        int i;
        quicksort(data, 0, SIZE-1);
        for (i=0; i<SIZE; i++)
               printf("%d ", data[i]);
        printf("\n");
}

void quicksort(int list[], int left, int right)
{
    int i, last;
    int temp;

    if (left >= right)
        return;

    last = left;
    for (i=left+1; i <= right; i++){
        if (list[i] < list[left] ){
            last++;
            temp=list[last];
            list[last]=list[i];
            list[i]=temp;
        }
    }

    temp=list[left];
    list[left]=list[last];
    list[last]=temp;

    quicksort(list, left, last-1);
    quicksort(list, last+1, right);
}