【競技プログラミング】C++でカウントソートの問題を解いたのでまとめる

今回は、『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』で使用されているAIZU ONLINE JUDGEより、カウントソートについて勉強したのでまとめておきます。

問題を解くのに使ってるC++言語は、Udemyの動画で勉強しました。

カウントソートについて

カウントソートとは、整列したい列の値が0からk-1の整数に限定されている状況において、それぞれの整数の登場頻度の累積を計算することで整列を行うソートアルゴリズムです。

分布数え上げソートとも呼ばれ、上記の説明を言い換えると、ソート対象のデータをキーにして、キーの出現回数とその累積度数分布を計算して利用することで整列するものとなります。
キーとなるデータがとりうる値の範囲が限定されている必要があります。

計算量は、O(N)です。

参考にした問題は1-6-A Counting Sortです。

回答に必要な情報は以下の4つです。

・整列元の整数が格納された配列、A
・整数の取りうる値の範囲k(この問題の場合は、0 ≤ A[i] ≤ 10,000)
・数え上げ用の配列、B
・整列作業用の配列、C

この問題をC++で解くと以下のようなコードになります。

#include <iostream>
#include <vector>

#define K 10000

using namespace std;
int N;
vector<int> A;
vector<int> B;
vector<int> C;

void counting_sort(){
    for (int i = 0; i <= K; i++){
        C.push_back(0);
    }
    for (int j = 0; j < A.size(); j++){
        C[A[j]] = C[A[j]] + 1;
    }
    for (int i = 0; i <= K; i++){
        if (C[i] > 0){
            while (C[i] > 0){
                B.push_back(i);
                C[i] = C[i] - 1;
            }
        }
    }
}

int main()
{
    cin.tie(0);

    int n;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> n;
        A.push_back(n);
    }

    counting_sort();
    
    for (int i = 0; i < B.size(); i++)
    {   
        if (i < B.size() - 1){
            cout << B[i] << " ";
        }else{
            cout << B[i] << "n";
        }
    }
    return 0;
}

まとめ

久々に自力で解けたのでとてもうれしい。

競プロはAtCorderの水色を目指して勉強してます。
アルゴリズムは主にこの本を読みながら勉強してます。

[kattene]
{
“image”: “https://m.media-amazon.com/images/I/51GbST65OIL.jpg”,
“title”: “プログラミングコンテスト攻略のためのアルゴリズムとデータ構造”,
“description”: “”,
“sites”: [
{
“color”: “orange”,
“url”: “https://amzn.to/3cHASaL”,
“label”: “Amazon”,
“main”: “true”
}
]
}
[/kattene]