AOJ ALDS1 6_A（Couting Sort）を解く

Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の6_A問題をC++で解いてみました。

ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#6「ソート」では、実用的なソートアルゴリズムについて紹介します。

問題（6_A: Couting Sort）

問題はリンク先をご覧ください。

AOJ ALDS1 6_A問題: Couting Sort

計数ソートについて学びます。

計数ソートについて

与えられた数列を、値の範囲を表す配列に格納します。例えば、次の数列

a[0] = 2, a[1] = 5, a[2] = 1, a[3] = 3, a[4] = 2, a[5] = 3, a[6] = 0

を値の範囲を表す配列 c に格納すると、その値は、

c[0] = 0, c[1] = 1, c[2] = 2, c[3] = 2, c[4] = 0, c[5] = 1

となります。c を求めることができれば、c の要素を小さい順番に出力していけば、ソートした結果を得ることができます。これは入力例1と出力例1になっています。

計数ソートの特徴は、以下です。

• 値の範囲を大きくすることができない。値の範囲が大きくなると配列を確保することが難しくなります。
• 数列の大きさを n、値の範囲の大きさを k とすると計算量は、$O(n + k)$ となります。
• （実装にも依存しますが）安定的なソートです。

C++ プログラム例（ALDS1 6_A）

読み込んだ配列 a を値の範囲の大きさを表す配列 c に格納します（16ー19行目）。c の要素を小さい方から配列 b に格納しなおして（21ー28行目）、出力します。

以下が、C++プログラムとなります。

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

#define N_MAX 10000

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	vector<int> c(N_MAX + 1, 0);
	for (int i = 0; i < n; ++i) {
		++c[a[i]];
	}

	vector<int> b(n);
	int index = 0;
	for (int i = 0; i <= N_MAX; ++i) {
		for (int j = 0; j < c[i]; ++j) {
			b[index] = i;
			++index;
		}
	}

	for (int i = 0; i < n; ++i) {
		cout << b[i] << " \n"[i == n - 1];
	}

	return 0;
}

上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。

最後に

一番最初の 1_A問題、トピック#2 で初歩的なソートアルゴリズムについて学びました。実用的なアルゴリズムとしては、5_B問題でマージソートを紹介しました。

今回のトピック#6 では、マージソートに続き、実用的なソートアルゴリズムを紹介します。この記事で紹介した計数ソートは、値の範囲に制約がありますが、うまく問題の設定があえば、計算量も少なくソートできます。

引き続き、ALDS1 の問題を紹介していきます。