プログラム 技術

クイックソートを理解する

学生時代に習ったソートアルゴリズムを改めてまとめたものとなります

クイックソートって？

ソートアルゴリズムの1つでソートアルゴリズムの中で処理速度が一番速いものとなっています。ただ、条件などによっては他のソートアルゴリズムの方が速い場合があります。詳しくは以下のサイトがわかりやすいと思います

参考サイト
クイックソートのアルゴリズムをわかりやすく解説します！ | Webpia
クイックソートのアルゴリズムをわかりやすく解説します！ | Webpia

アルゴリズムを勉強している方に向けて、「クイックソートとは何なのか？」「どのようなアルゴリズムなのか？」についてわかりや ...

続きを読む

ソート用の配列を生成する

ソートの動作確認用に1～100までのランダムな数字を持つ配列を生成します

std::vector<int> RandomCreate() {
    std::set<int> uniqueNumbers; // 重複を防ぐためにstd::setを使用
    std::vector<int> numberArray; // 返却用変数

    // 乱数生成器の初期化
    std::random_device rd;
    std::mt19937 gen(rd());

    // 1から100までのランダムな数字を生成
    std::uniform_int_distribution<int> distribution(1, 100);

    while (uniqueNumbers.size() < 10) {
        int randomNumber = distribution(gen);

        // 重複を防ぐために挿入前に確認
        if (uniqueNumbers.find(randomNumber) == uniqueNumbers.end()) {
            uniqueNumbers.insert(randomNumber);
        }
    }

    // 生成したランダムな数字を表示
    std::cout << "Unique Random Numbers: ";
    for (int number : uniqueNumbers) {
        std::cout << number << " ";
        // 返却用変数に代入する
        numberArray.push_back(number);
    }
    std::cout << std::endl;

    // ランダムにシャッフルする
    std::shuffle(numberArray.begin(), numberArray.end(), gen);

    return numberArray;
}

ランダムな数字が生成されて、順番もいい感じにばらけました

クイックソートを実装する

それでは実際にクイックソートをC＋＋で実装してみます

template <typename T>
void QuickSort(std::vector<T>& arr, int low, int high) {
    if (low < high) {
        // arr[pi] は現在の基準値の位置
        int pi = partition(arr, low, high);

        std::cout << "Midway Array(quickSort): ";
        for (int i : arr) {
            std::cout << i << " ";
        }
        std::cout << std::endl;

        // 基準値を基に再帰的にソートを行う
        quickSort(arr, low, pi - 1);
        std::cout << "Midway Array(quickSort): ";
        for (int i : arr) {
            std::cout << i << " ";
        }
        std::cout << std::endl;

        quickSort(arr, pi + 1, high);
        std::cout << "Midway Array(quickSort): ";
        for (int i : arr) {
            std::cout << i << " ";
        }
        std::cout << std::endl;
    }
}

まずは再帰的に呼び出す関数を用意します。配列の入れ替えを実施する関数は別で用意します

template <typename T>
int Partition(std::vector<T>& arr, int low, int high) {
    T pivot = arr[high];  // 基準値を最後の要素とする
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        // 現在の要素が基準値以下であれば、i をインクリメントし、要素を swap する
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }

    // 基準値を正しい位置に移動し、その位置を返す
    std::swap(arr[i + 1], arr[high]);

    std::cout << "Midway Array(partition): ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return i + 1;
}

最期に配列の中身を入れ替える関数を実装します

実際に動かしてみる

検証用の配列を作成し、それをクイックソートで並び替えて結果を見てみましょう

std::vector<int> arr = RandomCreate();
int n = arr.size();

std::cout << "Original Array: ";
for (int i : arr) {
    std::cout << i << " ";
}
std::cout << std::endl;

quickSort(arr, 0, n - 1);

std::cout << "Sorted Array: ";
for (int i : arr) {
    std::cout << i << " ";
}
std::cout << std::endl;

クイックソートを用いて配列が並び変えられていることが確認できました

会社紹介

私が所属しているアドバンスド・ソリューション株式会社(以下、ADS)は一緒に働く仲間を募集しています

会社概要
「技術」×「知恵」＝顧客課題の解決・新しい価値の創造

この方程式の実現はADSが大切にしている考えで、技術を磨き続けるgeekさと、顧客を思うloveがあってこそ実現できる世界観だと思っています
この『love & geek』の精神さえあれば、得意不得意はno problem！
技術はピカイチだけど顧客折衝はちょっと苦手。OKです。技術はまだ未熟だけど顧客と知恵を出し合って要件定義するのは大好き。OKです
凸凹な社員の集まり、色んなカラーや柄の個性が集まっているからこそ、常に新しいソリューションが生まれています

ミッション
私たちは、テクノロジーを活用し、業務や事業の生産性向上と企業進化を支援します

ホームページ
アドバンスド・ソリューション株式会社
アドバンスド・ソリューション株式会社

アドバンスド・ソリューションは主にMicrosoft製品を使用して、企業の生産性向上に取り組んでいます。要件定義から導入 ...

サイトへ移動
お問い合わせ
お問い合わせ | アドバンスド・ソリューション株式会社
お問い合わせ | アドバンスド・ソリューション株式会社

お問い合わせはこちら

-プログラム, 技術
-