C++の壺・ソート篇

　単純比較ソートでは、要素の先頭から順に二つの値を比較してデータを入れ替えます。その手順は下表のようになります。ちなみに、比較回数は、常に、「要素数×（要素数−１）÷２」 となります。

[手順]	[1]	[2]	[3]	[4]	* 赤字 : 比較元、青字 : 比較先
1回目の比較	7	3	9	1	(1)と(2)を比較（7の方が大きいので入れ替え）
2回目の比較	3	7	9	1	(1)と(3)を比較（7の方が小さいのでそのまま）
3回目の比較	3	7	9	1	(1)と(4)を比較（3の方が大きいので入れ替え）
4回目の比較	1	7	9	3	(2)と(3)を比較（7の方が小さいのでそのまま）
5回目の比較	1	3	9	7	(2)と(4)を比較（7の方が大きいので入れ替え）
6回目の比較	1	3	9	7	(3)と(4)を比較（9の方が大きいので入れ替え）
[ソート終了]	1	3	7	9	* 降順の場合は大小を逆にして比較

　実際にデータを入れ替える時は、退避先の変数を一つ用意する必要があります。そこに二つのいずれかの値を退避させておいてから、順に値を代入していきます。

// 二つの値を入れ替え void exchange(int *n1, int *n2) { int temp; // 退避用の変数 temp = *n1; *n1 = *n2; *n2 = temp; }

#include <stdio.h> void main() { int a[] = {10, 99}; exchange(&a[0], &a[1]); printf("a[0] = %d\n", a[0]); // =99 printf("a[1] = %d\n", a[1]); // =10 }

　以上の二つのしくみを組み合わせてソートを行います。関数にすると以下のようになります。ここでは、for文を入れ子にして構成しています。なお、昇順と降順の違いは不等号の向きの違いだけです。

// 昇順ソート void sort(int *array, int length) { int i; // 比較元のインデックス int j; // 比較先のインデックス for (i=0; i<length-1; i++) { for (j=i+1; j<length; j++) { if (array[i] > array[j]) { // 入れ替え int temp = array[i]; array[i] = array[j]; array[j] = temp; } } } }	// 降順ソート void reverse(int *array, int length) { int i; // 比較元のインデックス int j; // 比較先のインデックス for (i=0; i<length-1; i++) { for (j=i+1; j<length; j++) { if (array[i] < array[j]) { // 入れ替え int temp = array[i]; array[i] = array[j]; array[j] = temp; } } } }
// main 関数 int main() { int a[] = {7, 3, 9, 1, 5, 2, 6, 0, 8, 4}; // 並べ替えるデータ int i; sort(a, 10); // 昇順ソート for (i=0; i<10; i++) { printf("%d, ", a[i]); // 出力結果　[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,] } printf("\n"); reverse(a, 10); // 降順ソート for (i=0; i<10; i++) { printf("%d, ", a[i]); // 出力結果　[ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0,] } if (getch()) return 0; }

　クイックソートは、基準値を設定して、その値を元にソートを行うもので、その名の通り高速でのソートが可能です。しかし、要素数が少ない時は効果は希薄です。逆に要素数が多ければ多いほど、単純なソートよりも早く並べ替えを行います。

手順	7, 3, 9, 1, 5, 2, 6, 0, 8, 4	備考
(1)基準値（任意に抽出した値の平均）	7, 3, 9, 1, 5, 2, 6, 0, 8, 4	(int)(7+4)/2 = 5
(2)基準値より大きい値を前から探す	7, 3, 9, 1, 5, 2, 6, 0, 8, 4	赤色 : 比較元
(3)基準値より小さい値を後ろから探す	7, 3, 9, 1, 5, 2, 6, 0, 8, 4	青色 : 比較先
(4)見つかったら二つの値を交換	4, 3, 9, 1, 5, 2, 6, 0, 8, 7	交錯していたら(6)へ
(5)前後の添え字を一つずつ進める	4, 3, 9, 1, 5, 2, 6, 0, 8, 7	(2)〜(4)の繰返し
↓	↓	...
(6)両者が交錯したところでストップ	4, 3, 0, 1, 5, 2, 6, 9, 8, 7	←赤と青が逆転
(7)交錯地点で配列を二分化	4, 3, 0, 1, 5, 2 / 6, 9, 8, 7	以降はそれぞれに処理
(8)再帰処理	2, 3, 0, 1/ 5, 4/ 6, 9, 8, 7	(1)〜(7)の繰返し
↓	↓	...
・ソート終了	0/ 1/ 2/ 3/ 4/ 5/ 6/ 7/ 8/ 9

　上記中、基準値の算出法は様々です。一例として二つの値の平均値を取っています。また、下記のサンプルコードも一例にすぎません。様々な記述やアレンジが可能です。

// クイックソート関数
// ... *array : 並べ替える配列,　start : 開始インデックス,　end : 終了インデックス
// ... 戻り値 : 並べ替えた後の配列
void quicksort(int *array, int start, int end) 
{
    int i = start;    // 開始インデックス
    int j = end;      // 終了インデックス
    int base = (array[start] + array[end]) / 2;  // (1)基準値（平均値を適用）

    while(1) {
        while (array[i] < base) i++;       // (2)基準値より大きい値を前から探す
        while (array[j] > base) j--;       // (3)基準値より小さい値を後ろから探す
 
        if (i >= j) break;         // (6)両者が交錯したら抜ける（交換すべき値がない）

        // (4)処理が続いていれば値の交換（小さい値を前に、大きい値を後ろに）
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;

        i++;                          // (5)交換した一つ後にインデックスを進める
        j--;                          // (5)交換した一つ前にインデックスを進める
    }
    // (7)配列を二分化してそれぞれに (8)再帰処理
    if (start < i-1) quicksort(array, start, i-1);   // 基準値より小さいグループ
    if (end > j+1)  quicksort(array, j+1, end);     // 基準値より大きいグループ
} 

// main 関数
int main() 
{
    int a[] = {7, 3, 9, 1, 5, 2, 6, 0, 8, 4};    // 並べ替えるデータ

    quicksort(a, 0, 9);     // クイックソート（配列、最初のインデックス、最後のインデックス）

    int i;
    for (i=0; i<10; i++) {
        printf("%d, ", a[i]);   // 出力結果　[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,]
    }

    if (getch()) return 0;
} 	

　Cではクイックソートをパッケージ化した qsort関数が用意されています。ただし、比較用の関数をプログラマが別途定義する必要があります。

qsort function
・書式	void qsort( void *array, size_t len, size_t width, 　　int ( *compare ) (const void *value1, const void *value2 )
・機能	クイックソートの実行
・引数	array...配列、len...要素数、width...要素一個のバイト数、 compare...比較関数へのポインタ、 value1...比較元要素へのポインタ、value2...比較先要素へのポインタ
・戻り値	なし　（ただし、配列array を上書き）
・要件	stdlib.h または search.h のインクルード compare関数の戻り値（昇順時）は、 　*value1>*value2 の時は正の値、 　*value1==*value2 の時は0、 　*value1<*value2 の時は負の値である。（降順の時は正負逆）

　上記中、size_t は sizeof演算子の結果を表します。要素一個分のバイト数は、sizeof(データ型名) で取得できます。また、void* のところは、適宜データ型へのキャストを行うことができます。
　int (*compare)(...) は関数へのポインタです。引数なしの関数名は関数のアドレスを表しますので、実際の記述では引数の記述は必要ありません。

#include <stdio.h>     // printf使用
#include <stdlib.h>     // qsort使用
#include <conio.h>    // getch使用

// 比較関数 : 二つの int型の値を比較する
int compare(const void *value1, const void *value2)
{
    // 結果により、正の値、0、負の値のいずれかを返す
    return *(const int *)value1 - *(const int *)value2;
}

// main 関数
int main() 
{
    int a[] = {7, 3, 9, 1, 5, 2, 6, 0, 8, 4};    // 並べ替えるデータ
 
    qsort(a, 10, sizeof(int), compare);    // クイックソート

    int i;
    for (i=0; i<10; i++) {
        printf("%d, ", a[i]);    // 出力結果　[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,]
    }

    if (getch()) return 0;
}