完全理解への5ステップ！C言語でのクイックソート基礎から応用まで

はじめに

C言語を使ったクイックソートの基礎から応用までを完全理解するための5つのステップをご紹介します。

詳しい使い方、注意点、カスタマイズ方法も解説します。

手を動かしながら学べるサンプルコード付きで、一緒に学びましょう。

●C言語とは

C言語は、1972年にAT&Tベル研究所のデニス・リッチーによって開発された汎用プログラミング言語です。

その性能の高さと移植性の良さから、さまざまなオペレーティングシステムや組み込みシステムで広く利用されています。

また、C言語は直感的な文法と豊富な機能が魅力で、他の多くのプログラミング言語の基礎ともなっています。

●クイックソートとは

クイックソートは、効率的なソートアルゴリズムの一つで、その名の通り「高速」な処理が特徴です。

その働きを分かりやすく説明すると、「基準値（ピボット）を設け、それより大きな数と小さい数に分け（パーティション）、それぞれを再度同様に分ける」という手順を繰り返すことで、データ全体をソートします。

○クイックソートの基本的な考え方

クイックソートの基本的な考え方は「分割統治法」と呼ばれる手法に基づいています。

これは、大きな問題を小さな問題に分割し、それぞれを解決した後で結果を統合するというものです。

この手法を用いて、データをソートするというのがクイックソートです。

○クイックソートのアルゴリズム

具体的なアルゴリズムは次の通りです。

まず、データ群から一つをピボットとして選びます。

そして、データ群をピボットより小さい数と大きい数の二つに分けます。

これをパーティションと呼びます。

次に、それぞれのパーティションを再度同様に分けるという作業を再帰的に行います。

この作業を全てのデータがソートされるまで繰り返します。

●C言語でのクイックソートの基本的な実装

C言語でのクイックソートの基本的な実装について見ていきましょう。

○サンプルコード1：基本的なクイックソートの実装

クイックソートを行う基本的なC言語のコードを紹介します。

このコードでは、整数の配列をクイックソートする関数を定義しています。

#include <stdio.h>

void quicksort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quicksort(arr, low, pivot - 1);
        quicksort(arr, pivot + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high- 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quicksort(arr, 0, n-1);
    printf("Sorted array: \n");
    for (int i=0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

このプログラムでは、まずquicksort関数を使って配列をソートします。

そしてpartition関数で配列をピボットより小さい部分と大きい部分に分けています。

分けた後はそれぞれの部分をquicksort関数で再度ソートします。

この処理を全てのデータがソートされるまで再帰的に行っています。

上記のプログラムを実行すると、次のような結果が得られます。

Sorted array: 
1 5 7 8 9 10

この結果から、配列が正しくソートされていることがわかります。

●C言語でのクイックソートの応用例

クイックソートは、整数の配列だけでなく、文字列や構造体など、さまざまなデータのソートにも使用することができます。

その応用例をいくつか紹介していきます。

○サンプルコード2：文字列のクイックソート

まずは文字列のクイックソートの例です。

下記のコードは、文字列の配列をソートするクイックソートの実装例です。

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

void quicksort(char arr[][20], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quicksort(arr, low, pivot - 1);
        quicksort(arr, pivot + 1, high);
    }
}

int partition(char arr[][20], int low, int high) {
    char pivot[20];
    strcpy(pivot, arr[high]);
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (strcmp(arr[j], pivot) <= 0) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void swap(char* a, char* b) {
    char t[20];
    strcpy(t, a);
    strcpy(a, b);
    strcpy(b, t);
}

int main() {
    char arr[5][20] = {"apple", "banana", "kiwi", "mango", "pear"};
    int n = sizeof(arr)/sizeof(arr[0]);
    quicksort(arr, 0, n-1);
    printf("Sorted array: \n");
    for (int i=0; i < n; i++) {
        printf("%s ", arr[i]);
    }
    return 0;
}

このプログラムでは、配列のデータが文字列になっているので、partition関数やswap関数内で文字列を扱うための関数strcpyとstrcmpを使用しています。

これらはC言語の標準ライブラリに含まれる関数で、文字列のコピーや比較を行うことができます。

このプログラムを実行すると、次のような結果が得られます。

Sorted array: 
apple banana kiwi mango pear

このように、文字列の配列もアルファベット順に正しくソートされていることがわかります。

○サンプルコード3：構造体のクイックソート

次に、構造体のクイックソートの例を見てみましょう。

下記のコードは、構造体の配列をソートするクイックソートの実装例です。

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

typedef struct {
    char name[20];
    int age;
} Person;

void quicksort(Person arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quicksort(arr, low, pivot - 1);
        quicksort(arr, pivot + 1, high);
    }
}

int partition(Person arr[], int low, int high) {
    Person pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (strcmp(arr[j].name, pivot.name) <= 0) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void swap(Person* a, Person* b) {
    Person t = *a;
    *a = *b;
    *b = t;
}

int main() {
    Person arr[5] = {{"Taro", 30}, {"Jiro", 25}, {"Saburo", 20}, {"Shiro", 35}, {"Goro", 32}};
    int n = sizeof(arr)/sizeof(arr[0]);
    quicksort(arr, 0, n-1);
    printf("Sorted array: \n");
    for (int i=0; i < n; i++) {
        printf("%s ", arr[i].name);
    }
    return 0;
}

このプログラムでは、Personという構造体を定義し、その構造体の配列をソートしています。

このように、構造体の中の特定のメンバを基準にソートを行うことも可能です。

このプログラムを実行すると、次のような結果が得られます。

Sorted array: 
Goro Jiro Saburo Shiro Taro

これにより、Person構造体のnameメンバを基準にしたクイックソートが正しく動作していることが確認できます。

●クイックソートを使う際の注意点と詳細な対処法

クイックソートを使う際には、いくつかの注意点があります。

それぞれの注意点と、それに対する対処法を詳しく見ていきましょう。

○注意点1：最悪の場合の処理時間

クイックソートの処理時間は、データの初期配置によって変わります。最良の場合は、O(n log n)の処理時間でソートが完了します。

しかし、最悪の場合は、O(n^2)の処理時間がかかる可能性があります。

これは、ピボットの選び方が不適切な場合に発生します。例えば、すでにソ

ート済みのデータをクイックソートすると、最悪の場合の処理時間がかかります。

○対処法：最悪の場合の処理時間を改善する方法

これを改善する一つの方法は、ピボットをランダムに選択することです。

これにより、平均的な処理時間がO(n log n)に改善されます。

また、別の改善方法として、データの初期配置による処理時間の差を小さくする「イントロソート」というアルゴリズムを使用する方法もあります。

イントロソートは、クイックソートとヒープソートを組み合わせたソートアルゴリズムで、最悪の場合でもO(n log n)の処理時間を保証します。

○注意点2：安定性について

クイックソートは、「不安定なソート」の一つです。

つまり、同じ値を持つ要素の相対的な順序がソート後に保たれない可能性があります。

これは、データに特定の属性（例えば、時間スタンプやIDなど）による順序が重要な場合に問題となる可能性があります。

○対処法：安定なソートを行う方法

これに対する対処法としては、他の「安定なソートアルゴリズム」を併用することが考えられます。

例えば、「マージソート」や「バブルソート」などは安定なソートアルゴリズムであり、同じ値の要素の順序を保つことができます。

クイックソートで大まかにソートを行った後、安定なソートアルゴリズムで微調整を行う、といった使い方が考えられます。

●クイックソートのカスタマイズ方法

さて、ここまでクイックソートの基本的な使い方と注意点について見てきましたが、クイックソートはその柔軟性から、さまざまなカスタマイズが可能です。

ここでは、その中から2つのカスタマイズ例を紹介します。

○サンプルコード4：比較関数を自由に設定するクイックソート

まず、比較関数を自由に設定できるクイックソートの例を見てみましょう。

下記のコードでは、qsort関数を使ってクイックソートを行います。

qsort関数はC言語の標準ライブラリに含まれる関数で、比較関数を引数として受け取り、その比較関数に基づいてデータをソートします。

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

int compare(const void* a, const void* b) {
    int int_a = *((int*)a);
    int int_b = *((int*)b);

    if (int_a == int_b) return 0;
    else if (int_a < int_b) return -1;
    else return 1;
}

int main() {
    int arr[] = {4, 2, 5, 3, 1};
    int n = sizeof(arr)/sizeof(arr[0]);

    qsort(arr, n, sizeof(int), compare);

    printf("Sorted array: \n");
    for (int i=0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

このプログラムでは、比較関数compareを定義し、qsort関数に渡しています。

compare関数は2つの引数を取り、それらを比較して結果を返します。

この関数を使うことで、ソートの基準を自由に設定することができます。

例えば、逆順にソートしたい場合は、compare関数内で比較の方向を逆にすればよいのです。

このプログラムを実行すると、次のような結果が得られます。

Sorted array: 
1 2 3 4 5

これにより、比較関数を自由に設定することで、様々な条件下でのクイックソートが可能であることがわかります。

○サンプルコード5：並列処理を利用したクイックソート

次に、並列処理を利用したクイックソートの例を見てみましょう。

下記のコードでは、OpenMPという並列処理ライブラリを使ってクイックソートを行います。

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

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quicksort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);

        #pragma omp parallel sections
        {
            #pragma omp section
            quicksort(arr, low, pivot - 1);
            #pragma omp section
　　　　　　　　　　　quicksort(arr, pivot + 1, high);
        }
    }
}

int main() {
    int arr[] = {4, 2, 5, 3, 1};
    int n = sizeof(arr)/sizeof(arr[0]);

    quicksort(arr, 0, n-1);

    printf("Sorted array: \n");
    for (int i=0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

このプログラムでは、quicksort関数内で#pragma omp parallel sectionsディレクティブを使用し、2つの部分配列のソートを並列に行うように指定しています。

これにより、マルチコアプロセッサを利用した高速なソートが可能になります。

このプログラムを実行すると、次のような結果が得られます。

Sorted array: 
1 2 3 4 5

これにより、並列処理を利用することで、大量のデータに対するクイックソートも高速に行うことが可能であることがわかります。

ただし、並列処理を行う際には、プログラムの複雑性が増す点や、並列化によるオーバーヘッドが発生する点に注意が必要です。

まとめ

クイックソートの基礎から応用までをC言語で完全に理解するための5つのステップについて詳しく解説しました。

この記事では、クイックソートの基本的な使い方、その注意点と対処法、そしてカスタマイズの方法をサンプルコードを交えて説明しました。

まず、クイックソートの基本的な使い方について解説しました。

このプログラムでは、配列を2つの部分配列に分割し、ピボットより小さい要素は左の部分配列に、ピボットより大きい要素は右の部分配列に分ける方法を用いています。

その後、これらの部分配列を再帰的にソートすることで、全体の配列がソートされます。

次に、クイックソートの注意点について説明しました。

クイックソートは非常に高速なソートアルゴリズムですが、一部のデータに対しては最悪の場合の処理時間がかかること、またクイックソートは「不安定なソート」であるため、同じ値を持つ要素の相対的な順序がソート後に保たれないことがあります。

これらの問題に対する対処法として、ピボットをランダムに選択することや、安定なソートアルゴリズムを併用することなどが考えられます。

最後に、クイックソートのカスタマイズの方法について説明しました。

一つ目の例では、比較関数を自由に設定することができるクイックソートを紹介しました。

この比較関数を利用することで、ソートの基準を自由に設定することができます。

二つ目の例では、並列処理を利用したクイックソートを紹介しました。

並列処理を利用することで、大量のデータに対するクイックソートを高速に行うことが可能になります。

以上が、C言語を使ったクイックソートの基礎から応用までの解説です。

この情報を利用して、クイックソートの理解と実践を深めていただければ幸いです。