6日でできる 新C言語入門｜バブルソートとqsortの基本

6日でできる 新C言語入門｜バブルソートとqsortの基本

データを並べ替えると、見つけやすく、比べやすく、扱いやすくなる。
バブルソートで仕組みを学び、qsortで実用的な並べ替えへ進もう。

プログラムでは、配列に入ったデータを並べ替えたい場面がよくあります。

たとえば、点数を低い順に並べる、価格を安い順に並べる、単語を辞書順に並べる、といった処理です。このように、データを決められた順序に並べ替える処理をソートと呼びます。

ソートは、プログラミングの中でもとても基本的で重要な処理です。データを並べ替えることで、最大値や最小値を見つけやすくなったり、検索しやすくなったり、一覧表示を見やすくしたりできます。

C言語では、ソートの仕組みを自分で実装することもできますし、標準ライブラリのqsortを使って並べ替えることもできます。

自分で実装する代表例として、バブルソートがあります。バブルソートは、隣り合う要素を比べて、順番が逆なら交換していく分かりやすいアルゴリズムです。処理効率は高くありませんが、ソートの基本的な考え方を学ぶにはとても向いています。

一方、qsortはC言語の標準ライブラリに用意されている汎用的なソート関数です。整数配列だけでなく、文字列配列や構造体配列など、比較関数を工夫することでさまざまなデータを並べ替えられます。

この記事では、ソートの基本、バブルソートの仕組み、C言語での実装、qsortの使い方、比較関数の考え方、文字列ソートまで、サンプルプログラムを使ってやさしく解説していきます。

ソートとは何か

ソートとは、複数のデータを決められた順序に並べ替える処理です。

代表的な並べ方には、昇順と降順があります。

たとえば、次のような配列があるとします。

5 3 8 2

これを昇順に並べ替えると、次のようになります。

2 3 5 8

降順に並べ替えると、次のようになります。

8 5 3 2

ソートは、単にきれいに並べるだけではありません。
データの整理、検索、ランキング表示、統計処理など、さまざまな処理の土台になります。

主なソートアルゴリズム

ソートには、いろいろな方法があります。

バブルソート、選択ソート、挿入ソートは、仕組みが比較的分かりやすい反面、データ数が多くなると処理回数が増えやすいです。

クイックソートやマージソートは、より効率のよい並べ替えに使われます。

C言語の標準ライブラリにはqsortという汎用ソート関数があります。名前からクイックソートを連想しやすいですが、実際に内部でどのアルゴリズムを使うかは処理系に任されています。使う側としては、比較関数を渡して並べ替え条件を指定することが重要です。

図：ソートはデータを決められた順序に並べ替える処理

この図から分かること

この図から分かるのは、ソートが配列の中身を決められた順序に並べ替える処理だということです。

整列前のデータはバラバラに並んでいますが、ソート処理を行うことで、昇順や降順のように見やすい順序へ整理できます。データを並べ替えると、比較や検索、一覧表示がしやすくなります。

バブルソートとは何か

バブルソートは、隣り合う要素を比べて、必要なら交換する処理を繰り返すソートアルゴリズムです。

昇順に並べたい場合は、左の値が右の値より大きければ交換します。

たとえば、次のような配列を考えます。

64 92 75 48 88 70

昇順にしたい場合、隣り合う値を左から順番に比較します。

1回の大きな繰り返しが終わると、大きい値が右端へ移動していきます。

この様子が泡のように大きな値が端へ浮かんでいくイメージに近いため、バブルソートと呼ばれます。

バブルソートの処理の流れ

バブルソートの昇順処理は、次のような流れです。

昇順では、大きい値が右側に移動していきます。
そのため、1回目の繰り返しが終わると、右端には最大値が置かれます。

次の繰り返しでは、右端の値はすでに決まっているため、比較範囲を1つ減らせます。

バブルソートをC言語で実装する

次のプログラムでは、点数の配列をバブルソートで昇順に並べ替えます。

プロジェクト/ファイル名： Lesson71_1/main.c

#include <stdio.h>

#define SIZE 6

void show(int*);
void swap(int*, int*);

int main(void) {
    int scores[SIZE] = { 64, 92, 75, 48, 88, 70 };
    int i, j;

    printf("初期配列: ");
    show(scores);

    // バブルソートで昇順に並べ替える
    for (i = 0; i < SIZE - 1; i++) {
        for (j = 0; j < SIZE - i - 1; j++) {
            if (scores[j] > scores[j + 1]) {
                swap(&scores[j], &scores[j + 1]);
            }
        }

        printf("途中経過: ");
        show(scores);
    }

    printf("整列後: ");
    show(scores);

    return 0;
}

// 配列の内容を表示する関数
void show(int* array) {
    int i;

    for (i = 0; i < SIZE; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

// 2つの整数を入れ替える関数
void swap(int* x, int* y) {
    int temp;

    temp = *x;
    *x = *y;
    *y = temp;
}

実行結果

初期配列: 64 92 75 48 88 70
途中経過: 64 75 48 88 70 92
途中経過: 64 48 75 70 88 92
途中経過: 48 64 70 75 88 92
途中経過: 48 64 70 75 88 92
途中経過: 48 64 70 75 88 92
整列後: 48 64 70 75 88 92

このプログラムでは、scores配列を昇順に並べ替えています。

int scores[SIZE] = { 64, 92, 75, 48, 88, 70 };

バブルソートの中心は、2重のfor文です。

for (i = 0; i < SIZE - 1; i++) {
    for (j = 0; j < SIZE - i - 1; j++) {
        if (scores[j] > scores[j + 1]) {
            swap(&scores[j], &scores[j + 1]);
        }
    }
}

内側のfor文では、隣り合う要素を比較しています。

scores[j] > scores[j + 1]

左側の値が右側の値より大きい場合、昇順としては順番が逆です。
そのため、swap関数で2つの値を入れ替えます。

swap(&scores[j], &scores[j + 1]);

swap関数には、配列要素のアドレスを渡しています。
関数内で値を入れ替えるため、ポインタ渡しを使っています。

交換処理を関数に分ける理由

バブルソートでは、2つの値を入れ替える処理が何度も出てきます。

そこで、swap関数として分けておくと、処理の意味が分かりやすくなります。

void swap(int* x, int* y) {
    int temp;

    temp = *x;
    *x = *y;
    *y = temp;
}

この関数では、一時変数tempを使って、xが指す値とyが指す値を入れ替えています。

配列の要素を関数内で変更したいので、swap関数には値そのものではなくアドレスを渡しています。

バブルソートの途中経過を読む

実行結果を見ると、1回目の途中経過で最大値の92が右端へ移動しています。

途中経過: 64 75 48 88 70 92

次の繰り返しでは、右端の92はすでに確定しているため、それより左側を比較していきます。
2回目が終わると、88が92の左側に移動しています。

途中経過: 64 48 75 70 88 92

このように、バブルソートでは、大きい値が右側へ少しずつ移動していきます。

図：バブルソートは隣り合う要素を比較して交換する

この図から分かること

この図から分かるのは、バブルソートが隣り合う2つの要素を比べながら進むということです。

昇順では、左側の値が右側の値より大きい場合に交換します。この処理を何度も繰り返すことで、大きい値が右側へ移動し、最終的に配列全体が小さい順に整列されます。

バブルソートの特徴

バブルソートは、仕組みが分かりやすいアルゴリズムです。

バブルソートの計算量は、一般的にO(n²)です。
データ数が増えると、比較回数が大きく増えます。

そのため、大量データの実用的なソートには向かないことが多いです。
ただし、ソートの基本を理解するにはとても良い題材です。

qsortとは何か

qsortは、C言語の標準ライブラリに用意されている汎用ソート関数です。

stdlib.hを読み込むことで使えます。

#include <stdlib.h>

#include <stdlib.h>

qsortは、整数配列だけでなく、文字列配列や構造体配列など、さまざまな型の配列を並べ替えられます。

ただし、qsortは配列の中身がどのような型なのかを直接知りません。
そのため、1要素のサイズと、並び順を決める比較関数を渡す必要があります。

qsortの基本形は次の通りです。

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

qsortを使うときのポイントは、比較関数です。

比較関数が、どちらの要素を前に置くべきかを判断します。

qsortの比較関数の考え方

qsortの比較関数は、2つの要素を比べて、戻り値で順序を伝えます。

整数を昇順に並べる比較関数は、次のように書けます。

int compareAsc(const void* left, const void* right) {
    const int* a = (const int*)left;
    const int* b = (const int*)right;

    if (*a < *b) {
        return -1;
    }
    if (*a > *b) {
        return 1;
    }
    return 0;
}

leftとrightはconst void型です。
そのままではint型の値として扱えないため、const intへ変換しています。

const int* a = (const int*)left;
const int* b = (const int*)right;

そのあと、aとbを比較して、どちらを前に置くかを戻り値で伝えています。

qsortで整数配列を昇順に並べる

次のプログラムでは、価格の配列をqsortで昇順に並べ替えます。

プロジェクト/ファイル名： Lesson71_2/main.c

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

#define SIZE 6

int compareAsc(const void*, const void*);
void show(int*);

int main(void) {
    int prices[SIZE] = { 320, 150, 980, 420, 75, 600 };

    printf("初期配列: ");
    show(prices);

    // qsortで昇順に並べ替える
    qsort(prices, SIZE, sizeof(int), compareAsc);

    printf("ソート後: ");
    show(prices);

    return 0;
}

// qsortに渡す比較関数
int compareAsc(const void* left, const void* right) {
    const int* a = (const int*)left;
    const int* b = (const int*)right;

    if (*a < *b) {
        return -1;
    }
    if (*a > *b) {
        return 1;
    }
    return 0;
}

// 配列の内容を表示する関数
void show(int* array) {
    int i;

    for (i = 0; i < SIZE; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

実行結果

初期配列: 320 150 980 420 75 600
ソート後: 75 150 320 420 600 980

このプログラムでは、prices配列をqsortで昇順に並べ替えています。

qsort(prices, SIZE, sizeof(int), compareAsc);

この呼び出しを分解すると、次のようになります。

qsortは、配列の要素を比較するときにcompareAscを呼び出します。
compareAscが返す値によって、要素の順番が決まります。

比較関数で引き算だけにしない理由

整数の比較関数では、次のように引き算で書かれる例を見かけることがあります。

return *(int*)left - *(int*)right;

小さな値だけを扱う学習用では分かりやすいこともありますが、大きな整数を扱うと、引き算の結果がint型の範囲を超える可能性があります。

そのため、安全に書くなら、大小比較をif文で分ける方法がおすすめです。

if (*a < *b) {
    return -1;
}
if (*a > *b) {
    return 1;
}
return 0;

この書き方なら、差を計算せずに順序だけを返せます。

qsortとバブルソートの違い

バブルソートとqsortは、どちらも配列を並べ替えるために使えますが、考え方が違います。

バブルソートは、ソートの仕組みを学ぶために向いています。
qsortは、実際に配列を効率よく並べ替えたいときに便利です。

図：qsortは比較関数を使って並び順を決める

この図から分かること

この図から分かるのは、qsortが比較関数を使って並び順を決めるということです。

qsort自身は、要素の型や並べたい条件を詳しく知っているわけではありません。配列の先頭アドレス、要素数、1要素のサイズ、比較関数を受け取り、比較関数を呼び出しながら要素の順序を決めます。比較関数を変えることで、昇順、降順、文字列順、構造体の特定メンバ順などに対応できます。

qsortで文字列を辞書順に並べる

qsortは、整数だけでなく文字列の配列にも使えます。

文字列を並べ替える場合は、strcmpを使って比較します。
strcmpを使うには、string.hを読み込みます。

#include <string.h>

文字列配列をqsortで並べるときは、少しポインタの形に注意が必要です。

たとえば、次のような配列があります。

const char* words[SIZE] = {
    "delta",
    "apple",
    "cherry",
    "banana",
    "echo"
};

wordsの各要素は、文字列を指すポインタです。
qsortの比較関数には、配列要素のアドレスが渡されます。つまり、文字列そのものではなく、文字列ポインタのアドレスが渡されます。

そのため、比較関数では次のように受け取ります。

const char* const* a = (const char* const*)left;
const char* const* b = (const char* const*)right;

そして、aとbをstrcmpで比較します。

return strcmp(*a, *b);

qsortで文字列配列を並べるプログラム

次のプログラムでは、英単語の配列を辞書順に並べ替えます。

プロジェクト/ファイル名： Lesson71_3/main.c

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

#define SIZE 5

int compareWord(const void*, const void*);
void showWords(const char*[]);

int main(void) {
    const char* words[SIZE] = {
        "delta",
        "apple",
        "cherry",
        "banana",
        "echo"
    };

    printf("初期: ");
    showWords(words);

    // qsortで文字列を辞書順に並べ替える
    qsort(words, SIZE, sizeof(words[0]), compareWord);

    printf("ソート後: ");
    showWords(words);

    return 0;
}

// 文字列ポインタ同士を比較する関数
int compareWord(const void* left, const void* right) {
    const char* const* a = (const char* const*)left;
    const char* const* b = (const char* const*)right;

    return strcmp(*a, *b);
}

// 文字列配列の内容を表示する関数
void showWords(const char* array[]) {
    int i;

    for (i = 0; i < SIZE; i++) {
        printf("%s ", array[i]);
    }
    printf("\n");
}

実行結果

初期: delta apple cherry banana echo
ソート後: apple banana cherry delta echo

このプログラムでは、words配列をqsortで並べ替えています。

qsort(words, SIZE, sizeof(words[0]), compareWord);

sizeof(words[0])は、配列の1要素のサイズを表します。
wordsの1要素は文字列ポインタなので、文字列そのものの長さではなく、ポインタ1個分のサイズです。

比較関数compareWordでは、strcmpを使って文字列を比較しています。

return strcmp(*a, *b);

strcmpは、文字列を辞書順に比較し、左の文字列が前なら負の値、同じなら0、後ろなら正の値を返します。
qsortの比較関数の戻り値ルールに合っているため、そのまま使えます。

文字列ソートで注意したいこと

文字列配列のqsortでは、比較関数のポインタの扱いが少し難しく感じやすいです。

整数配列の場合、qsortに渡されるのはint要素のアドレスです。

一方、文字列配列の場合、配列要素は文字列ポインタです。
qsortに渡されるのは、その文字列ポインタのアドレスです。

そのため、文字列比較では、const char* const*のような形で受け取り、aやbをstrcmpへ渡します。

この部分は最初に少し難しく見えますが、文字列配列の要素はポインタであり、比較関数にはその要素のアドレスが渡る、と考えると整理しやすくなります。

昇順と降順を切り替える考え方

qsortでは、比較関数を変えることで並び順を切り替えられます。

整数を昇順にする場合は、左が小さいときに負の値を返します。

if (*a < *b) {
    return -1;
}

降順にしたい場合は、戻り値の考え方を逆にします。

if (*a > *b) {
    return -1;
}
if (*a < *b) {
    return 1;
}
return 0;

つまり、どちらを前に置きたいかを比較関数で決める、という考え方です。

qsortは、比較関数を工夫することで、さまざまな並び替えに対応できます。

qsortを使うときの注意点

qsortは便利ですが、いくつか注意したいポイントがあります。

stdlib.hを読み込む

qsortを使うには、stdlib.hが必要です。

#include <stdlib.h>

これを忘れると、qsortの宣言が見つからず、警告やエラーにつながることがあります。

要素数と要素サイズを正しく指定する

qsortでは、要素数と1要素のサイズを正しく指定する必要があります。

qsort(prices, SIZE, sizeof(int), compareAsc);

整数配列ならsizeof(int)でもよいですが、より配列に合わせて書くならsizeof(prices[0])も使えます。

qsort(prices, SIZE, sizeof(prices[0]), compareAsc);

配列の型が変わったときにも対応しやすい書き方です。

比較関数の型を合わせる

qsortに渡す比較関数は、次の形に合わせます。

int compare(const void*, const void*);

戻り値はintです。
引数はconst void*を2つ受け取ります。

比較関数の中で、必要な型へ変換して比較します。

比較関数で元データを書き換えない

比較関数は、2つの要素の順序を判断するための関数です。
基本的には、比較対象のデータを書き換えないようにします。

引数がconst void*になっているのも、比較のために参照するだけという意図があります。

バブルソートとqsortをどう学び分けるか

バブルソートとqsortは、どちらか一方だけを覚えればよいというものではありません。

学習では、まずバブルソートでソートの仕組みを理解するとよいです。
隣り合う要素を比較し、順番が逆なら交換するという流れは、ソートの基本を目で追いやすいからです。

そのうえで、qsortを学ぶと、C言語で実用的なソートを行う方法が見えてきます。

バブルソートで原理を理解し、qsortで実用的な書き方を覚えると、ソート処理への理解が深まります。

ソートを理解するとデータ処理が広がる

ソートは、C言語のデータ処理でとてもよく使われる考え方です。

数値を並べ替えるだけでなく、文字列、構造体、ファイルから読み込んだデータなどにも応用できます。

Lesson71_1では、バブルソートで隣接比較と交換の流れを確認しました。
Lesson71_2では、qsortを使って整数配列を昇順に並べ替えました。
Lesson71_3では、qsortとstrcmpを使って文字列配列を辞書順に並べ替えました。

ソートは、配列、ポインタ、関数、関数ポインタ、文字列といったC言語の重要な要素がつながるテーマです。
バブルソートで仕組みを理解し、qsortで実用的な並べ替えに慣れていくと、データを扱うプログラムの幅が大きく広がります。