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

クイックソート解説ページのアイキャッチ

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

ソートとは

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

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

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

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

ソートの説明図

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

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

スポンサーリンク

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

さて、ここで皆さんに少し考えてみていただきたいのですが、あなたなら上の図のような数字の並びを、どのようなアルゴリズム(手順)で昇順に並び替えますか?

私が最初に思い浮かんだアルゴリズムは下記のようなものです。

  • まず1番目に大きい数字(9)を見つける
  • その1番目に大きい数字を右から1番目の数字と入れ替える
  • 次に2番目に大きい数字(8)を見つける
  • その2番目に大きい数字を右から2番目の数字と入れ替える
  • 次に3番目に大きい数字(7)を見つける
  • その3番目に大きい数字を右から3番目の数字と入れ替える
  • 以下、全ての数字が昇順に並ぶまで同様の手順を繰り返す

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

ソートのアルゴリズムの例

単純なアルゴリズムなので、このアルゴリズムを思いついた方も多いのではないかと思います。

このアルゴリズムは有名なソートのアルゴリズムである「選択ソート」に当てはまります。

もしかしたら他のアルゴリズムを思いついた方もいるかもしれません。

ソートには様々なアルゴリズムが存在し、同じルールに従って数字を並べ替える場合でも、様々なアルゴリズムで同じ並び替え結果を得る事が可能です。

例えばですが、ソートには下記のようなアルゴリズムがあります。

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

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

クイックソートとは

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

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

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

クイックソートの考え方

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

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

  • 閾値を決める
  • データの集合を2つのデータの集合に分割する
    • 閾値以下(or 未満)のデータを集めた集合
    • 閾値以上(or 超える)のデータを集めた集合
  • 2つの集合をそれぞれ個別にソートする

図を用いてもう少しこの考え方を解説していきます。

閾値を決める

まずは閾値を決めます。

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

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

Pivotの決定

MEMO

Pivot は前述の通り、データの集合の中にあれば、どのデータを選んでもソート結果に影響はありません

ただしソートを行うために必要な計算量(比較量)がこの Pivot によって変わります

一番効率的にソートを行うためには集合内の中央値を Pivot に採用するのが良いです

しかし中央値を探索するのに余計な計算量が必要になってしまいますので、逆に非効率なこともあります

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

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

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

集合の分割

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

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

左側からの探索

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

右側からの探索

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

見つかったデータの交換

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

データの探索と交換

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

データの探索と交換の終了

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

より具体的には、左側からの探索範囲を1つ狭めた単位に Pivot 以下のデータ、右側からの探索範囲を1つ狭めた範囲に Pivot 以上のデータが集まります。

分割した集合の範囲

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

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

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

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

分割した集合のソート

ここがクイックソートの考え方のポイントです。

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

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

クイックソートです。

つまり、左側の集合のみ・右側の集合のみをそれぞれを新たなデータ全体と捉えて、それぞれに対してクイックソートを行います。

  • 閾値を決める
  • データの集合を2つのデータの集合に分割する
    • 閾値以下(or 未満)のデータを集めた集合
    • 閾値以上(or 超える)のデータを集めた集合
  • 2つの集合をそれぞれ個別にソートする

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

分割した集合の分割

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

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

分割した集合の分割2

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

MEMO

データ数が1つになるだけでなく、既にソートが完了している集合についても分割できなくなるはずです

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

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

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

クイックソートでソートが行われていく様子

スポンサーリンク

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

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

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

quicksort.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;

    /* ソートを行う範囲が1以下の場合 */
    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;
        }

        /* 探索した2つの数字を交換 */
        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 関数は下記の3つの引数を受け取るように行っています。

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

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

  • a[left]a[right] まで

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

分割終了の判断
/* ソートを行う範囲が1以下の場合 */
if(left >= right) {
    return;
}

閾値を決める

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

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

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

スポンサーリンク

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

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

集合の分割
/* 探索範囲の初期化 */
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;
    }

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

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

}

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

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

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

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

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

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

分割した集合の範囲

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

分割終了の判断
/* ソートを行う範囲が1以下の場合 */
if(left >= right) {
    return;
}

まとめ

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

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

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

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

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

他のソートアルゴリズムであるマージソートについても下記ページで解説しています。マージソートの方が考え方は簡単かな?ソートに興味のある方は是非こちらも読んでみてください。

マージソート解説ページのアイキャッチマージソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)

2 COMMENTS

Kちゃん

めちゃめちゃわかりやすかったです。
ありがとうございます^^

細かいかもしれませんが
コード内のコメントの以上、以下という言葉は、その数を含むので、
「より大きい」「より小さい」「未満」といった言葉に置き換えた方が正確です。

“`
/* pivot以上の数字を左側から探索 */
“`

これからもよろしくおねがいします。

返信する
daeu

Kちゃん

コメントありがとうございます。

下記部分ですかね?

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

確かにコメントが間違ってましたので修正しました…。

・修正前

/* pivot以下の数字を左側から探索 */

・修正後

/* pivot以下の数字を右側から探索 */

この記事を書くにあたって一番書きにくかったのが “以上” と “より大きい”、”以下” と “より小さい” の使い分けだったんですよね…。

pivot 自体はどちらの集合にあっても良いので、あえて2つの集合を “pivot 以上の集合” と “pivot 以下の集合” と記載していますが、交換後の pivot がどちらに入るかによって、本当はどちらかの集合は “より大きい” or “より小さい” 集合になることになります。
ですが、この辺りはぼかして、”pivot 以上の集合” と “pivot 以下の集合” で統一して記載します。
もしかしたらここがちょっと混乱するかもなーと心配してます。

「pivot 未満のデータの集合」は「pivot 以下のデータの集合」の部分集合になるはずなので、「pivot 以下のデータの集合」に統一するのは間違いではないと思っていますが、もっとうまく書く方法があったのかもしれないです…。

返信する

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です