【C言語】乱数の配列をクイックソートする方法を解説

2023年9月10日

目次から探す

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

クイックソートは、効率的なソートアルゴリズムの一つです。

以下では、クイックソートのアルゴリズムの概要を説明します。

ステップ1: ピボットの選択

クイックソートでは、ソート対象の配列からピボットとなる要素を選びます。

一般的には、配列の先頭、末尾、または中央の要素をピボットとして選びます。

ステップ2: パーティション

選ばれたピボットを基準に、配列を2つの部分に分割します。

ピボットより小さい要素は左側に、ピボットより大きい要素は右側に配置します。

この操作をパーティションと呼びます。

ステップ3: 再帰的なソート

パーティションによって分割された2つの部分配列に対して、再帰的にクイックソートを適用します。

各部分配列に対して、ピボットを選び、パーティションを行い、再帰的にソートを行います。

この再帰的な処理を繰り返すことで、全体の配列がソートされます。

乱数の配列をクイックソートする方法

ここでは、乱数の配列をクイックソートする方法について解説します。

乱数の配列の生成

まず、乱数の配列を生成する必要があります。

C言語では、rand関数を使用して乱数を生成することができます。

以下のコードは、指定した要素数の乱数の配列を生成する例です。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void generateRandomArray(int array[], int size) {
    srand(time(NULL)); // 乱数のシードを設定
    for (int i = 0; i < size; i++) {
        array[i] = rand() % 100; // 0から99までの乱数を生成
    }
}
int main() {
    int size = 10; // 配列の要素数
    int array[size];
    generateRandomArray(array, size);
    // 生成された配列の表示
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

クイックソートの実装

次に、乱数の配列をクイックソートするための実装を行います。

以下のコードは、クイックソートを実装した例です。

#include <stdio.h>
void quickSort(int array[], int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = array[left]; // ピボットを左端の要素とする
    int i = left + 1;
    int j = right;
    while (1) {
        while (i <= right && array[i] < pivot) {
            i++;
        }
        while (j >= left + 1 && array[j] > pivot) {
            j--;
        }
        if (i > j) {
            break;
        }
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i++;
        j--;
    }
    array[left] = array[j];
    array[j] = pivot;
    quickSort(array, left, j - 1);
    quickSort(array, j + 1, right);
}
int main() {
    int size = 10; // 配列の要素数
    int array[size];
    generateRandomArray(array, size);
    printf("ソート前の配列: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    quickSort(array, 0, size - 1);
    printf("ソート後の配列: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

実行例と結果の確認

上記のコードを実行すると、乱数の配列が生成され、クイックソートが適用された結果が表示されます。

以下は、実行例とその結果の一部です。

ソート前の配列: 45 12 78 34 56 23 90 87 65 43
ソート後の配列: 12 23 34 43 45 56 65 78 87 90

このように、乱数の配列をクイックソートすることで、要素が昇順にソートされます。