C++ で動的配列を使用した基数ソート

はじめに

この実験では、C++ で基数ソートアルゴリズムを実行して、動的配列を使用して配列をソートします。基数ソートは、異なる位置の個々の桁を処理することでソートするソートアルゴリズムです。

ライブラリのインクルードと関数の設定

まず、~/project ディレクトリに main.cpp という名前の C++ ファイルを作成します。iostream と vector ライブラリをインクルードし、整数の std::vector を受け取る radix_sort 関数を設定します。

#include <iostream>
#include <vector>
using namespace std;

void radix_sort(vector<int>& nums) {

}

getMax 関数を定義する

整数のベクトルを入力として受け取り、最大値を返すget_max関数を定義します。

int get_max(vector<int>& nums) {
    int max = nums[0];
    for(int i = 1; i < nums.size(); i++) {
        if(nums[i] > max)
            max = nums[i];
    }
    return max;
}

CountingSort 関数を定義する

整数のベクトル、現在の桁の値を表す整数値、および出力用の整数のベクトルを受け取るcounting_sort関数を定義します。この関数は、カウントソートアルゴリズムを使用して、現在の桁の値に基づいてベクトルをソートします。

void counting_sort(vector<int>& nums, int place, vector<int>& output) {
    const int max = 10;
    int count[max];

    for(int i = 0; i < max; i++)
        count[i] = 0;

    for(int i = 0; i < nums.size(); i++)
        count[(nums[i] / place) % 10]++;

    for(int i = 1; i < max; i++)
        count[i] += count[i - 1];

    for(int i = nums.size() - 1; i >= 0; i--) {
        output[count[(nums[i] / place) % 10] - 1] = nums[i];
        count[(nums[i] / place) % 10]--;
    }

    for(int i = 0; i < nums.size(); i++)
        nums[i] = output[i];
}

基数ソート関数を定義する

整数のベクトルを入力として受け取るradix_sort関数を定義します。この関数は、入力ベクトルから最大値を取得し、各桁の値に基づいてcounting_sort関数を使用してベクトルをソートします。

void radix_sort(vector<int>& nums) {
    int max = get_max(nums);

    for(int place = 1; max / place > 0; place *= 10) {
        vector<int> output(nums.size());
        counting_sort(nums, place, output);
    }
}

テスト

radix_sort関数をテストするには、テスト用のベクトルを作成して表示するmain関数を作成します。

int main() {
    vector<int> test = {121, 432, 564, 23, 1, 45, 788};
    radix_sort(test);

    for(int num : test)
        cout << num << " ";
    cout << endl;

    return 0;
}

コンパイルと実行

端末で以下のコマンドを使用してプログラムをコンパイルして実行します。

g++ main.cpp -o main &&./main

以下の出力が表示されるはずです。

1 23 45 121 432 564 788

まとめ

この実験では、C++ で動的配列を使用して基数ソートアルゴリズムを実行する方法を学びました。基数ソートアルゴリズムは、異なる位置の個々の桁を処理することで機能し、整数や文字列に対して一般的に使用されるソートアルゴリズムです。