クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

このページではソートとクイックソートについて解説し、さらにC言語でクイックソートを実装したプログラムとそのプログラムの説明をしていきたいと思います。

ソートとは

このサイトでソートに関して解説を行うのは初めてなので、まずは簡単にソートについて解説したいと思います。

ソートとはデータを並び替えること

ソートについてご存知の方はコチラをクリックしてクイックソートとはの節までジャンプしていただいて問題ないです。

まず、ソートとはデータの集合をあるルールに従って並び替えることを言います。

ルールとは、例えば「数字を昇順に」「数字を降順に」「アルファベット順に」など、どのようにデータの集合を並び替えるかを決めるものです。

このページでは特に「数字を昇順に」並び替えるソートに焦点を当てて解説を行います。

スポンサーリンク

様々なソートのアルゴリズム

さて、ここで皆さんに少し考えてみていただきたいのですが、先程お見せした下の図のような並び替えを、あなたならどのような方法で昇順に並び替えますか？

私が最初に思い浮かんだ方法は下記のようなものです。

• まず１番目に大きい数字（９）を見つける
• その１番目に大きい数字を右から１番目の数字と入れ替える
• 次に２番目に大きい数字（８）を見つける
• その２番目に大きい数字を右から２番目の数字と入れ替える
• 次に３番目に大きい数字（７）を見つける
• その３番目に大きい数字を右から３番目の数字と入れ替える
• 以下、全ての数字が昇順に並ぶまで同様の手順を繰り返す

図で表すと下のような感じです。

単純な方法なので、この方法を思いついた方も多いのではないかと思います。

この方法は有名なソートである「選択ソート」に当てはまります。

私はこの方法を思いつきましたが、他の方法で並び替えを行なった方もおられるかと思います。

実は、同じ並び替え結果を得るにしても、それを実現するための方法はたくさん存在します。ソートにおけるこの” 方法” のことををソートアルゴリズムと呼びます。

例えばですが、ソートアルゴリズムには下記のようなものがあり、アルゴリズムによって特徴（メリットやデメリットなど）が異なります。

• 選択ソート
• 挿入ソート
• ヒープソート
• マージソート
• バブルソート
• クイックソート

ここから紹介する「クイックソート」も、このソートアルゴリズムの１つです。

ではこのクイックソートがどのようなアルゴリズムなのかについて解説していきたいと思います。

クイックソートとは

クイックソートとは、前述の通りソートのアルゴリズムの１つです。

他のソートアルゴリズムに比較して、下記のような特徴が挙げられます。

• 処理が高速（データの並びや Pivot の選び方によって遅い場合もある）
• 省メモリ（配列１つ分でソートが可能）

クイックソートの考え方

実は、クイックソートの考え方は分かりやすいです。

クイックソートはデータ全体を集合に分割しながら、集合単位でソートを行っていくソートアルゴリズムになります。

クイックソートでは、まずデータ全体の集合を下記の２つの集合に分割します（閾値と同じ値のデータはどちらの集合に含まれても良い）。

• 閾値以上のデータの集合
• 閾値以下のデータの集合

このように分割すれば、前者の全データは、後者の全データよりも小さい（もしくは同じ）という関係が成立します。つまり集合単位で見るとソートできていることになります。

ですので、各集合のデータを個別にソートして最後にくっつけてやればデータ全体のソートが完了することになります。

各集合のデータをソートする際も同様に、下記のように集合を分割すれば、また新たに分割した集合も集合の単位でソートできたことになります。

• 閾値以上のデータの集合
• 閾値以下のデータの集合

また同様に分割すれば、さらに小さな集合が集合の単位でソートできることになり、これを繰り返していけば、最終的には各集合に１つのデータしか含まれないようになります。

「集合単位でソートされている＆集合に１つしかデータがない」ので、これでデータ単位でソートできたことになります。

つまり、クイックソートは下記によりソートを行うアルゴリズムになります。

• 閾値を決める
• データの集合を２つのデータの集合に分割して集合単位でソートする
  • 閾値以下（or 未満）のデータを集めた集合
  • 閾値以上（or 超える）のデータを集めた集合
• ２つの集合をそれぞれ個別に同様の方法でソートする

スポンサーリンク

クイックソートの処理

では、具体的にどのようにしてこのクイックソートを実現するのかについて、図と実例を用いて解説していきたいと思います。

閾値を決める

まずは閾値を決めます。

ソートを実現する上で、この閾値はデータの集合の中にあるものであれば何でも良いです。この閾値はクイックソートでは Pivot と呼ばれます。

このページでは集合の一番左側にあるデータを Pivot とすることにしたいと思います。

データの集合を２つのデータの集合に分割する

次はこの Pivot 以下のデータを集合の左側に、Pivot 以上のデータを集合の右側に集めます。

Pivot 以下のデータと Pivot 以上のデータに分割するとなると、Pivot 自体のデータをどちら側に含めるか迷ってしまうかもしれませんが、Pivot 自体はどちら側に含まれてもソート結果に影響はありません。どちらに含まれても問題なしです。

このデータの集合の分割は、下記のようにして行う事ができます。

まずデータ全体の左端から順に Pivot 以上のデータを探索します。

Pivot 以上のデータが見つかったら、次はデータ全体の右端から順に Pivot 以下のデータを探索します。

続いて、見つかった２つのデータを交換します。

今度は交換した２つの内側のデータに対し、同様に Pivot 以下のデータと Pivot 以下のデータを探索し、見つかったら２つのデータを交換する。これを繰り返していきます。

データの左端から開始した探索の探索範囲と、データの右端から開始した探索の探索範囲が重なったら、データの交換をやめ、分割の処理を終了します。

これを行うことで、左側には Pivot 以下のデータ、右側には Pivot 以上のデータが集まることになります（Pivot 自体のデータはどちらかに含まれる）。

より具体的には、左側からの探索範囲を１つ狭めた範囲（下の図の赤矢印をデータ１つ分左側に狭めた範囲）に Pivot 以下のデータ、右側からの探索範囲を１つ狭めた範囲（下の図の青矢印をデータ１つ分右側に狭めた範囲）に Pivot 以上のデータが集まります。

２つの集合をそれぞれ個別にソートする

ここで、左側の集合（Pivot 以下のデータの集合）と右側の集合（Pivot 以上のデータの集合）のデータに注目してみましょう。

左側の集合の全てのデータは右側の集合のデータよりも小さい事が確認できると思います（そうなるようにデータを集めたので当たり前なのですが…）。

つまり、最初に説明したように集合単位のソートが完了したことになります。

なので、左側の集合のソートと右側の集合のソートをそれぞれ行えば、データ全体がソートされることになります（Pivot のデータはどちらに含まれていてもこれは変わりません。これが Pivot のデータをどちらに集めても問題ない理由です）。

ここが最初にも説明したクイックソートの考え方のポイントです。

データ全体を小さく分割し、分割後のデータを個別にソートすることで、データ全体のソートを行うのがクイックソートです。

では分割した集合のデータのソートはどのようにして行えば良いでしょうか？

クイックソートです。

つまり、左側の集合のみ・右側の集合のみをそれぞれを新たなデータ全体と捉えて、それぞれに対してクイックソート（ここまで解説してきた内容の処理）を行います。

• 閾値を決める
• データの集合を２つのデータの集合に分割して集合単位でソートする
  • 閾値以下（or 未満）のデータを集めた集合
  • 閾値以上（or 超える）のデータを集めた集合
• ２つの集合をそれぞれ個別に同様の方法でソートする

例えば、左側の集合に対してさらにクイックソートを行っていくと、下記のようにさらに集合が分割されます。

この２つの集合においても、それぞれの集合で個別にソートを行えば、全体のソートが実現できる事が確認できると思います。

さらに左側の集合に対してクイックソートを行ってみましょう。次は下の図のように集合が分割されます。

今度は集合のデータ数が１つになりました。集合が２つに分割できなくなった時点で分割の処理は完了です。分割できなくなった時点で、その集合はソートが完了していることになります。

上の図においても、２つの集合のデータがしっかり昇順にソートされている事が確認できると思います。

こんな感じで、集合をどんどん Pivot 以下のデータの集合と Pivot 以上のデータの集合（Pivot となるデータ自体はどちらの集合に含めても良い）に細かく分割し、集合を分割できなくなるまで分割することを繰り返すのがクイックソートです。

下記は集合がどんどん分割され、その中でソートが進んでいく様子です。緑の数字は Pivot、ピンクの数字はソートが完了したものを表しています。

クイックソートのプログラム

クイックソートがどんなものであるかはイメージできてきたと思います。

次はクイックソートを行うC言語プログラムを紹介します。

#include <stdio.h>

/* データの数 */
#define NUM 10

/* 数字を入れ替える関数 */
void swap(int *a, int *b) {
    int tmp;
    tmp = *b;
    *b = *a;
    *a = tmp;
}

/* クイックソートを行う関数 */
void quickSort(int a[], int left, int right) {
    int pivot;
    int i, j;

    /* ソートを行う範囲が１以下の場合 */
    if(left >= right) {
        return;
    }

    /* pivot の決定 */
    pivot = a[left];

    i = left;
    j = right;

    /* pivot以下の数字を配列の前半に
       pivot以上の数字を配列の後半に集める */
    while(1) {
        /* pivot以上の数字を左側から探索 */
        while (a[i] < pivot) {
            i++;
        }

        /* pivot以下の数字を右側から探索 */
        while (a[j] > pivot) {
            j--;
        }

        /* i >= j になったということは
           配列の左側にpivot以下の数字が、
        　　配列の右側にpivot以上の数字が集まったということ */
        if (i >= j) {
            /* 集合の分割処理は終了 */
            break;
        }

        /* 探索した２つの数字を交換 */
        swap(&(a[i]), &(a[j]));

        /* 交換後の数字の次から探索再開 */
        i++;
        j--;

    }

    /* 小さい数字を集めた範囲に対してソート */
    quickSort(a, left, i - 1);

    /* 大きい数字を集めた範囲に対してソート */
    quickSort(a, j + 1, right);

}

/* 配列を初期化する関数 */
void initArray(int a[]) {
    a[0] = 5;
    a[1] = 0;
    a[2] = 9;
    a[3] = 7;
    a[4] = 1;
    a[5] = 6;
    a[6] = 3;
    a[7] = 8;
    a[8] = 4;
    a[9] = 2;
}

/* 配列のデータを表示する関数 */
void printArray(int a[], int num){
    int i;
    for (i = 0; i < num; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int main(void) {
    int array[NUM];

    /* 配列を初期化 */
    initArray(array);

    /* ソート前の配列の表示 */
    printArray(array, NUM);

    /* クイックソート */
    quickSort(array, 0, NUM-1);

    /* ソート後の配列の表示 */
    printArray(array, NUM);

    return 0;

}

プログラムの解説

最後に上記のプログラムを「クイックソートの考え方」に照らし合わせて解説していきたいと思います。

クイックソートを行っているのは quickSort 関数です。

quickSort 関数は下記の３つの引数を受け取るように行っています。

• a[]：ソートを行うデータの集合（int 型の配列）
• left：ソートを行う範囲の左端を表す数字（int 型）
• right：ソートを行う範囲の右端を表す数字（int 型）

この quickSort 関数ではこれらの引数に対し、下記の範囲のデータのソートを行います。

• a[left] 〜 a[right] まで

left と right が同じ or 大小関係が反転している場合はもうデータの集合の分割ができませんので、直ちに関数を終了するようにしています。

/* ソートを行う範囲が１以下の場合 */
if(left >= right) {
    return;
}

スポンサーリンク

閾値を決める

quickSort 関数では、まず閾値（Pivot）の決定を行います。

ソートを行う範囲の左端のデータを Pivot としています。

/* pivot の決定 */
pivot = a[left];

データの集合を２つのデータの集合に分割する

続いてデータの集合を、閾値以下のデータの集合と閾値以上のデータの集合に分割します。

/* 探索範囲の初期化 */
i = left;
j = right;

/* pivot以下の数字を配列の前半に
   pivot以上の数字を配列の後半に集める */
while(1) {
    /* pivot以上の数字を左側から探索 */
    while (a[i] < pivot) {
        i++;
    }

    /* pivot以下の数字を左側から探索 */
    while (a[j] > pivot) {
        j--;
    }

    /* i >= j になったということは
       配列の左側にpivot以下の数字が、
    　 配列の右側にpivot以上の数字が集まったということ */
    if (i >= j) {
        /* 集合の分割処理は終了 */
        break;
    }

    /* 探索した２つの数字を交換 */
    swap(&(a[i]), &(a[j]));

    /* 交換後の数字の次から探索再開 */
    i++;
    j--;

}

分割をどのように行うかについてはデータの集合を２つのデータの集合に分割するで詳しく解説していますので、そちらを参考にしていただければと思います。

２つの集合をそれぞれ個別にソートする

最後に quickSort 関数の中で、分割した集合それぞれに対して quickSort 関数を実行します（再帰呼び出し）。

/* 小さい数字を集めた範囲に対してソート */
quickSort(a, left, i - 1);

/* 大きい数字を集めた範囲に対してソート */
quickSort(a, j + 1, right);

分割する際に左側からの探索と右側からの探索を行いますが、この探索範囲を１つ分狭めた範囲が、次に quickSort を行う範囲になります。

このように再帰的に quickSort を実行することでどんどん集合が分割されていきますが、分割できなくなった際には quickSort 関数冒頭の下記部分でその集合の分割が止まるようになっています。

/* ソートを行う範囲が１以下の場合 */
if(left >= right) {
    return;
}

スポンサーリンク

まとめ

このページではソートアルゴリズムの１つであるクイックソートについて解説を行いました。

考え方としては、特に再帰処理を理解している方にとっては割と分かりやすいアルゴリズムなのではないかと思います。

ただ実装はちょっと難しいですね…。特に集合を分割する処理と、分割する集合の範囲を決定する処理の実装は苦労しました…。

このページでも示したような図を実際に書きながらプログラムの動きを追うと実装しやすいと思います。

まず考え方を理解し、自分で実際にクイックソートを実装してみるとかなり力はつくと思いますので、是非お試しください！

本サイトでは、クイックソート以外にも下記のソートについても解説しています。

• マージソート
• 選択ソート
• 挿入ソート

下記リンク先でそれぞれについて解説していますので、他のソートアルゴリズムにも興味のある方は是非こちらも読んでみてください！

マージソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

選択ソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

挿入ソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）