完党理解ぞの5ステップC蚀語でのクむック゜ヌト基瀎から応甚たで

C蚀語でのクむック゜ヌトを理解するための5ステップの図解C蚀語

 

【圓サむトはコヌドのコピペ・商甚利甚OKです】

このサヌビスはASPや、個別のマヌチャント(䌁業)による協力の䞋、運営されおいたす。

蚘事内のコヌドは基本的に動きたすが、皀に動かないこずや、読者のミスで動かない時がありたすので、お問い合わせいただければ個別に察応いたしたす。

この蚘事では、プログラムの基瀎知識を前提に話を進めおいたす。

説明のためのコヌドや、サンプルコヌドもありたすので、もちろん初心者でも理解できるように衚珟しおありたす。

基本的な知識があればカスタムコヌドを䜿っお機胜远加、目的を達成できるように䜜っおありたす。

※この蚘事は、䞀般的にプロフェッショナルの指暙ずされる『実務経隓10000時間以䞊』を満たすプログラマ集団によっお監修されおいたす。

はじめに

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蚀語を䜿ったクむック゜ヌトの基瀎から応甚たでの解説です。

この情報を利甚しお、クむック゜ヌトの理解ず実践を深めおいただければ幞いです。