クイックソート

ソートのアルゴリズムのうち高速なアルゴリズムとして知られているクイックソートについて解説する

１．クイックソート

与えられた数値配列についての昇順クイックソートは，与えられた配列を，「ある値未満のグループ」と「ある値以上のグループ」に分割し，それぞれのグループに対してクイックソートを適応する，という再帰で実現される。要素数が１つか2つ程度になったら，それ以上分割しないで，処理を行ない，元に戻ればよい。

ここで，ある値は，ピボット（pivot）と呼ばれ，配列の先頭の値が用いる。（配列の先頭を用いるのは，最悪の場合，ソートが非常に遅くなるので，配列の中央位置の値を使うことが多い。）

Fig.1 配列表現

グループに分ける時，最悪の場合は，すべての値が片側に偏ってしまうこともあるので，元と同じ大きさの新しい配列を２つ用意して２つのグループに分ければよい。
しかし，再帰で呼び出すことを考えると，毎回新しい配列を作っていたら，メモリを非常に多く消費してしまう。これを避けるため，元の１つの配列上で２つのグループに分ける手法を考える。

２．クイックソートのプログラミング

（１）配列の先頭をピボットとし，別の一時退避場所に退避させる。
　　（先頭（左端）に空席が出来た。）
（２）配列末尾（右端）から順にピボットと比較し，ピボット未満の値が１つ見つかったら，その値を左側の空席に移動する。
　　（今度は右側に空席が出来た。）
（３）左側の新しい数が入ってきた位置の１つ右隣から順にピボットと比較し，ピボット以上の値が１つ見つかったら，その値を右側の空席に移動する。
　　（今度は左側に空席が出来た。）
（４）「（２）」，「（３）」を繰り返し行ない，左右の比較位置が交わったら，繰り返しを終わる。この時，中間に空席が出来るので，退避させておいたピボットをその空席に戻す。

ここまでで分割が終了で，ピボットの左側には「ピボット値未満のグループ」ができ，右側には「ピボット値以上のグループ」が出来上がっている

（５）「ピボット値未満のグループ」と「ピボット値以上のグループ」についてクイックソートを呼び出せばよい。

List 1 クイックソートの関数（再帰）
x:クイックソート対象の先頭アドレス
num:配列要素数

void QuickSort(int *x, int num)
{
    int left,right,emptyPos;
    int pivot;
    int tmp;
    if (num<=1) return;
    if (num==2) {
        if (x[1]<x[0]) {
            tmp=x[0];
            x[0]=x[1];
            x[1]=tmp;
        }
        return;
    }

    pivot=x[0];
    left=0;
    right=num-1;
    /*x[left]が空要素の状態でスタート，pivotに個の要素のデータが退避しているとみなせる*/
    while (1) {
        while (pivot<=x[right] && left<right) right--;
        if (left<right) x[left++]=x[right]; /*x[right]が移動したので空になった*/
        else break;
        while (x[left]<=pivot && left<right) left++;
        if (left<right) x[right--]=x[left]; /*x[left]が移動したので空になった*/
        else break;
    }

    emptyPos=right;    /*whileループから抜け出てきたときにはleft==right，ここが空要素*/
    x[emptyPos]=pivot; /*退避してあったデータを空要素に入れる。この位置の要素は位置確定*/

    /*左右のグループに対して再帰呼び出し*/
    if (1<emptyPos) QuickSort(x,emptyPos);
    if (emptyPos<num-2) QuickSort(x+emptyPos+1,num-emptyPos-1);
}

３．クイックソートプログラム例

List.2 クイックソートプログラム例

#include "stdio.h"
#include "stdlib.h"

#define DEBUG
#define DEBUG2

#ifdef DEBUG
#define SIZE 20
#else
#define SIZE 2000
#endif

void makedata(int x[], int num)
{
int i;
for (i=0; i<num; i++) x[i]=rand()%(5*SIZE);
}

void printdata(int x[], int num)
{
    int i;
    for (i=0; i<num; i++) printf("%2d ",x[i]);
    printf("\n");
}

#ifdef DEBUG2
void printdata2(int x[], int num)
{
    int i;
    printf("=>");
    for (i=0; i<num; i++) printf("%2d ",x[i]);
    printf("\n");
}
#endif

/*小さい順ソート済みデータのチェック
　　返す値０：正常
　　　　　１：異常あり
*/
int checkSortedData(int x[], int num)
{
    int i;
    int ng=0;
    for (i=0; i<num-1; i++) {
        if (x[i+1]<x[i]) {
            printf("%2d %2d\n",x[i],x[i+1]);
            ng=1;
        }
    }
    return ng;
}

/*配列の要素数numの配列xをクイックソートする*/
void QuickSort(int *x, int num)
{
    int left,right,emptyPos;
    int pivot;
    int tmp;
    if (num<=1) return;
    if (num==2) {
        if (x[1]<x[0]) {
            tmp=x[0];
            x[0]=x[1];
            x[1]=tmp;
        }
        return;
    }
    pivot=x[0];
    left=0;
    right=num-1;
#ifdef DEBUG2
    printdata2(x, num);
#endif
    /*x[left]が空要素の状態でスタート，pivotに個の要素のデータが退避しているとみなせる*/
    while (1) {
        while (pivot<=x[right] && left<right) right--;
        if (left<right) x[left++]=x[right]; /*x[right]が移動したので空になった*/
        else break;
        while (x[left]<=pivot && left<right) left++;
        if (left<right) x[right--]=x[left]; /*x[left]が移動したので空になった*/
        else break;
    }
    emptyPos=right;    /*whileループから抜け出てきたときにはleft==right，ここが空要素*/
    x[emptyPos]=pivot; /*退避してあったデータを空要素に入れる。この位置の要素は位置確定*/
#ifdef DEBUG2
    printdata2(x, num);
#endif
    if (1<emptyPos) QuickSort(x,emptyPos);
    if (emptyPos<num-2) QuickSort(x+emptyPos+1,num-emptyPos-1);
}

#ifdef DEBUG
int main()
{
    int x[SIZE];
    int ng,i;
    for (i=0;i<10;i++) {
        makedata(x,SIZE);
        printdata(x,SIZE);
        QuickSort(x,SIZE);
        printdata(x,SIZE);
        ng=checkSortedData(x,SIZE);
        if (ng) printf("no good\n");
        else printf("good\n");
    }
}
#else
int main()
{
    int x[SIZE];
    int ng,i;
    for (i=0;i<1000;i++) {
        makedata(x,SIZE);
        QuickSort(x,SIZE);
        ng=checkSortedData(x,SIZE);
        if (ng) printf("no good\n");
    }
}
#endif

実行例の一部

41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36
=>41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36
=>36 27 34 0 27 24 5 41 62 64 58 45 81 78 61 91 95 42 69 67
=>36 27 34 0 27 24 5
=> 5 27 34 0 27 24 36
=> 5 27 34 0 27 24
=> 0 5 34 27 27 24
=>34 27 27 24
=>24 27 27 34
=>24 27 27
=>24 27 27
=>62 64 58 45 81 78 61 91 95 42 69 67
=>42 61 58 45 62 78 81 91 95 64 69 67
=>42 61 58 45
=>42 61 58 45
=>61 58 45
=>45 58 61
=>78 81 91 95 64 69 67
=>67 69 64 78 95 91 81
=>67 69 64
=>64 67 69
=>95 91 81
=>81 91 95
0 5 24 27 27 34 36 41 42 45 58 61 62 64 67 69 78 81 91 95
good

もし，すでにソート済のデータをクイックソートで並び変えると，再帰呼び出し回数が非常に多くなる可能性があるため，
並べ替え範囲の先頭の値をピボットにするのは望ましくない。
そこで，ソート済の場合でも，ソート前の場合でも均一な分割をするための工夫として，
配列の中央位置の値をピボットに使う場合は，次のように一箇所変更すればよい

List 3 クイックソートの関数（ピボットに中央位置の値を使う）
x:クイックソート対象の先頭アドレス
num:配列要素数

void QuickSort(int *x, int num)
{
    int left,right,emptyPos;
    int pivot;
    int tmp;
    if (num<=1) return;
    if (num==2) {
        if (x[1]<x[0]) {
            tmp=x[0];
            x[0]=x[1];
            x[1]=tmp;
        }
        return;
    }

    pivot=x[num>>1];
    x[num>>1]=x[0];
    x[0]=pivot;
    left=0;
    right=num-1;
    /*x[left]が空要素の状態でスタート，pivotに個の要素のデータが退避しているとみなせる*/
    while (1) {
        while (pivot<=x[right] && left<right) right--;
        if (left<right) x[left++]=x[right]; /*x[right]が移動したので空になった*/
        else break;
        while (x[left]<=pivot && left<right) left++;
        if (left<right) x[right--]=x[left]; /*x[left]が移動したので空になった*/
        else break;
    }

    emptyPos=right;    /*whileループから抜け出てきたときにはleft==right，ここが空要素*/
    x[emptyPos]=pivot; /*退避してあったデータを空要素に入れる。この位置の要素は位置確定*/

    /*左右のグループに対して再帰呼び出し*/
    if (1<emptyPos) QuickSort(x,emptyPos);
    if (emptyPos<num-2) QuickSort(x+emptyPos+1,num-emptyPos-1);
}

４．Ｃ標準ライブラリのクイックソート（１）

クイックソートを手軽に使えるようにするため，Ｃ言語では標準ライブラリとして提供されている。
昇順にソートしようとする時も降順にソートしようとする時も同じクイックソート関数を使うことができるように，２つのデータの比較方法を与える関数を別に定義し，標準ライブラリのクイックソート関数に，この比較関数を使ってほしいとお願いするプログラミングとなる。
クイックソート関数を使う場合は，「stdlib.h」をインクルードする。

qsort()はstdlib.h中で次のようにプロトタイプ宣言されている

void qsort(void *base, size_t num, size_t size, int (*compare)(const void*, const void*))

ここで「int (*compare)(const void*, const void*)」は「２つのデータの比較方法を与える」関数へのポインタであり，その返す値はint型である。
引数は2つあり，比較すべき２つのデータへのポインタとなっている。
なおこの比較関数の名前はcompareである必要はなく，なんでもよい。

List.4 標準ライブラリのクイックソート関数を使うプログラム例

#include "stdio.h"
#include "stdlib.h"

#define SIZE 20

void makedata(int x[], int num)
{
    int i;
    for (i=0; i<num; i++) x[i]=rand()%(5*SIZE);
}

void printdata(int x[], int num)
{
    int i;
    for (i=0; i<num; i++) printf("%2d ",x[i]);
    printf("\n");
}

/*小さい順ソート済みデータのチェック
　　返す値０：正常
　　　　　１：異常あり
*/
int checkSortedData(int x[], int num)
{
    int i;
    int ng=0;
    for (i=0; i<num-1; i++) {
        if (x[i+1]<x[i]) {
            printf("%2d %2d\n",x[i],x[i+1]);
            ng=1;
        }
    }
    return ng;
}

/*比較関数　　　　　昇順ソートの場合　*/
/*第一引数が小さい　：負の値を返す　　*/
/*第一引数が大きい　：正の値を返す　　*/
/*等しい　　　　　　：０を返す　　　　*/
int mycompfunc(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
    /*それぞれint型のポインタにキャストしてから，そのポインタ変数が指す値を使っている*/
}

int main()
{
    int x[SIZE];
    int ng;
    makedata(x,SIZE);
    printdata(x,SIZE);
    qsort(x,SIZE,sizeof(int),mycompfunc);
    /*    ソート対象配列　　　　　　　　　　        */
    /*      ソート対象配列のデータ数                */
    /*           ソート対象配列の１データのバイト数 */
    /*                       比較関数               */
    printdata(x,SIZE);
    ng=checkSortedData(x,SIZE);
    if (ng) printf("no good\n");
    else printf("good\n");
}

実行例

41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36
0 5 24 27 27 34 36 41 42 45 58 61 62 64 67 69 78 81 91 95
good

５．Ｃ標準ライブラリのクイックソート（２）

C標準ライブラリのクイックソートは比較関数仕様が柔軟にできているため（扱いにくいが），構造体のソートも比較関数をスイッチするだけでできる。
実はこのプログラム例は紹介のために示しているが，だめなプログラムである。このプログラムを理解してから次の「６」を見なさい。

List.5 標準ライブラリのクイックソート関数で構造体を扱うプログラム例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char name[32]; /*島の名前*/
    int population; /*島の人口*/
    double area;    /*島の面積[km2]*/
} island_t;

island_t Island[]={
    {"ぽこぽこ島", 1234, 5.3},
    {"ぷろげん島", 345, 1.2},
    {"ろんかい島", 5678, 4.5},
    {"いーらー島", 123, 3.4},
    {"それいけ島", 9874, 4.2},
    {"ぴっころ島", 874, 8.2}
};

void printData(island_t data[], int num, char *title)
{
    int i;
    puts(title);
    for (i=0; i<num; i++) {
        printf("%14s %6d %8.2lf\n",
         data[i].name, data[i].population, data[i].area);
    }
    printf("\n");
}

int compfuncName(const void *a, const void *b)
{
    return strcmp(((island_t*)a)->name,((island_t*)b)->name);
    /*island_t型のポインタにキャストしてからメンバnameで比較*/
}

int compfuncPopulation(const void *a, const void *b)
{
    return ((island_t*)a)->population - ((island_t*)b)->population;
    /*island_t型のポインタにキャストしてからメンバpopulationで比較*/
}

int compfuncArea(const void *a, const void *b)
{
    double comp;
    comp = ((island_t*)a)->area - ((island_t*)b)->area;
    /*island_t型のポインタにキャストしてからメンバareaで比較*/
    if (comp<0.) return -1;
    else if (0.<comp) return 1;
    else return 0;
}

int main()
{
    int DataSize=sizeof(island_t);
    int NumberOfDatas=sizeof(Island)/DataSize;
    printData(Island, NumberOfDatas, "初期状態");

    qsort(Island, NumberOfDatas, DataSize, compfuncName);
    printData(Island, NumberOfDatas, "名前順");

    qsort(Island, NumberOfDatas, DataSize, compfuncPopulation);
    printData(Island, NumberOfDatas, "人口順");

    qsort(Island, NumberOfDatas, DataSize, compfuncArea);
    printData(Island, NumberOfDatas, "面積順");

    return 0;
}

実行例

初期状態
    ぽこぽこ島   1234     5.30
    ぷろげん島    345     1.20
    ろんかい島   5678     4.50
    いーらー島    123     3.40
    それいけ島   9874     4.20
    ぴっころ島    874     8.20

名前順
    いーらー島    123     3.40
    それいけ島   9874     4.20
    ぴっころ島    874     8.20
    ぷろげん島    345     1.20
    ぽこぽこ島   1234     5.30
    ろんかい島   5678     4.50

人口順
    いーらー島    123     3.40
    ぷろげん島    345     1.20
    ぴっころ島    874     8.20
    ぽこぽこ島   1234     5.30
    ろんかい島   5678     4.50
    それいけ島   9874     4.20

面積順
    ぷろげん島    345     1.20
    いーらー島    123     3.40
    それいけ島   9874     4.20
    ろんかい島   5678     4.50
    ぽこぽこ島   1234     5.30
    ぴっころ島    874     8.20

６．Ｃ標準ライブラリのクイックソート（３）

「５」で示したプログラムで扱っているレコードサイズを考えてみよう。レコードとは，１つの島の持っているすべての情報のことであり，「名前」「人口」「面積」で構成されている。次のプログラムの冒頭で示されているように１つのレコードは48バイトで構成されている。（不思議*1）「５」で示したプログラムでは，レコードを並び替えるたびに48バイトを移動していたことになる。これでは，いくらクイックソートとはいえ，ソート速度は遅くなる。そこで，レコード番号の配列を作り，この番号の配列（int型を使ってもせいぜい4バイト）をソートするだけにすると，ソート速度を向上させることができる。例えば1レコードが数百バイトもあるようであれば，この改良は飛躍的な速度向上をもたらす。

不思議*1　このレコードの内部には，文字列32バイト，int型変数4バイト，double型変数8バイトしかなく，合計44バイトであった，しかし，コンパイラは，隙間に4バイトを使い，CPUが扱いやすい8の倍数でレコードを構成している。

List.6 標準ライブラリのクイックソート関数で構造体を扱い，インデックステーブルのみをソートするプログラム例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char name[32]; /*島の名前*/
    int population; /*島の人口*/
    double area;    /*島の面積[km2]*/
} island_t;

island_t Island[]={
    {"ぽこぽこ島", 1234, 5.3},
    {"ぷろげん島", 345, 1.2},
    {"ろんかい島", 5678, 4.5},
    {"いーらー島", 123, 3.4},
    {"それいけ島", 9874, 4.2},
    {"ぴっころ島", 874, 8.2}
};

int *index; /*ソートしたい配列の要素番号列を保存し，実際にソートされる配列*/
            /*動的に確保される*/

void printData(int index[], island_t data[], int num, char *title)
{
    int i;
    puts(title);
    for (i=0; i<num; i++) {
        printf("%14s %6d %8.2lf\n",
         data[index[i]].name, data[index[i]].population, data[index[i]].area);
    }
    printf("\n");
}

int compfuncName(const void *a, const void *b)
{
    return strcmp(Island[*(int *)a].name,Island[*(int *)b].name);
}

int compfuncPopulation(const void *a, const void *b)
{
    return (Island[*(int *)a].population-Island[*(int *)b].population);
}

int compfuncArea(const void *a, const void *b)
{
    double comp;
    comp = (Island[*(int *)a].area-Island[*(int *)b].area);
    if (comp<0.) return -1;
    else if (0.<comp) return 1;
    else return 0;
}

int main()
{
    int i;
    int DataSize=sizeof(int);
    int NumberOfDatas=sizeof(Island)/sizeof(island_t);
    printf("size of (int)= %d\n",sizeof(int));
    printf("size of (double)= %d\n",sizeof(double));
    printf("size of (island_t)= %d\n",sizeof(island_t));
    printf("\n");

    index=(int *)malloc(NumberOfDatas*sizeof(int));
    for (i=0; i<NumberOfDatas; i++) index[i]=i;
    printData(index, Island, NumberOfDatas, "初期状態");
    qsort(index, NumberOfDatas, DataSize, compfuncName);
    printData(index, Island, NumberOfDatas, "名前順");
    qsort(index, NumberOfDatas, DataSize, compfuncPopulation);
    printData(index, Island, NumberOfDatas, "人口順");
    qsort(index, NumberOfDatas, DataSize, compfuncArea);
    printData(index, Island, NumberOfDatas, "面積順");
    free(index);
    return 0;
}

実行例

size of (int)= 4
size of (double)= 8
size of (island_t)= 48

初期状態
    ぽこぽこ島   1234     5.30
    ぷろげん島    345     1.20
    ろんかい島   5678     4.50
    いーらー島    123     3.40
    それいけ島   9874     4.20
    ぴっころ島    874     8.20

名前順
    いーらー島    123     3.40
    それいけ島   9874     4.20
    ぴっころ島    874     8.20
    ぷろげん島    345     1.20
    ぽこぽこ島   1234     5.30
    ろんかい島   5678     4.50

人口順
    いーらー島    123     3.40
    ぷろげん島    345     1.20
    ぴっころ島    874     8.20
    ぽこぽこ島   1234     5.30
    ろんかい島   5678     4.50
    それいけ島   9874     4.20

面積順
    ぷろげん島    345     1.20
    いーらー島    123     3.40
    それいけ島   9874     4.20
    ろんかい島   5678     4.50
    ぽこぽこ島   1234     5.30
    ぴっころ島    874     8.20