Counting Sortの基本
Counting Sortは、整数の配列をソートするための効率的なアルゴリズムです。このアルゴリズムは、配列内の各要素の出現回数をカウントし、その情報を使用して配列をソートします。以下に、Counting Sortの基本的な手順を示します。
-
入力配列の最大値を見つける: Counting Sortは、入力配列の最大値に基づいて動作します。最初のステップは、配列内の最大値を見つけることです。
-
カウント配列を初期化する: 次に、最大値+1の長さを持つカウント配列を作成し、すべての要素を0に初期化します。
-
要素の出現回数をカウントする: 入力配列を左から右へと走査し、各要素の出現回数をカウント配列に記録します。
-
カウント配列を累積する: カウント配列を左から右へと走査し、各要素にその左側の要素の和を加えます。これにより、カウント配列の各要素は、その要素以下の値が入力配列に何回出現するかを示すようになります。
-
出力配列を生成する: 入力配列を右から左へと走査し、各要素をカウント配列を参照して適切な位置に配置します。配置後、対応するカウント配列の値を1減らします。
以上がCounting Sortの基本的な手順です。このアルゴリズムは、入力配列の要素が非負の整数で、その範囲が比較的小さい場合に最も効果的です。また、安定なソートアルゴリズムであるため、同じ値の要素の相対的な順序が保持されます。ただし、入力配列の最大値が非常に大きい場合、カウント配列のサイズが大きくなりすぎてメモリを大量に消費する可能性があるため、注意が必要です。
C++のVectorの使い方
C++のVectorは、動的配列を実装するためのSTL(Standard Template Library)の一部です。Vectorは、配列と同じように要素にアクセスできる一方で、動的にサイズを変更することが可能です。以下に、C++のVectorの基本的な使い方を示します。
-
Vectorの宣言: Vectorはテンプレートクラスなので、保存する要素の型を指定して宣言します。例えば、整数のVectorを宣言するには
std::vector<int> v;のようにします。 -
要素の追加:
push_back()関数を使用してVectorの末尾に要素を追加します。例えば、v.push_back(1);はVectorvの末尾に1を追加します。 -
要素のアクセス: 配列と同じように、インデックスを使用してVectorの要素にアクセスします。例えば、
v[0]はVectorvの最初の要素を返します。 -
サイズの取得:
size()関数を使用してVectorのサイズ（つまり、要素の数）を取得します。例えば、v.size();はVectorvのサイズを返します。 -
要素の削除:
erase()関数を使用してVectorから要素を削除します。erase()関数はイテレータを引数に取り、指定した位置の要素を削除します。
以上がC++のVectorの基本的な使い方です。Vectorは、サイズが動的に変更可能な配列を必要とする多くの場面で非常に便利です。ただし、Vectorの操作にはそれぞれ時間がかかることがあり、特に大きなデータを扱う場合にはパフォーマンスに影響を及ぼす可能性があるため、注意が必要です。
Counting SortとVectorの組み合わせ
C++のVectorとCounting Sortを組み合わせることで、動的な配列を効率的にソートすることが可能です。以下に、C++でVectorを使用してCounting Sortを実装する基本的な手順を示します。
- Vectorの宣言: まず、ソートしたい要素を保持するVectorを宣言します。また、Counting Sortのためのカウント配列もVectorで宣言します。
std::vector<int> input = { ... }; // ソートしたい要素
std::vector<int> count; // カウント配列
- カウント配列の初期化: 入力Vectorの最大値を見つけ、その値+1の長さを持つカウントVectorを作成します。すべての要素は0で初期化されます。
int max_val = *max_element(input.begin(), input.end());
count.resize(max_val + 1, 0);
- 要素の出現回数をカウント: 入力Vectorを走査し、各要素の出現回数をカウントVectorに記録します。
for (int num : input) {
count[num]++;
}
- カウントVectorを累積: カウントVectorを走査し、各要素にその左側の要素の和を加えます。
for (int i = 1; i < count.size(); i++) {
count[i] += count[i - 1];
}
- 出力Vectorを生成: 入力Vectorを逆順に走査し、各要素をカウントVectorを参照して適切な位置に配置します。配置後、対応するカウントVectorの値を1減らします。
std::vector<int> output(input.size());
for (int i = input.size() - 1; i >= 0; i--) {
output[count[input[i]] - 1] = input[i];
count[input[i]]--;
}
以上がC++のVectorを使用してCounting Sortを実装する基本的な手順です。この方法では、動的な配列を効率的にソートすることができます。ただし、入力Vectorの最大値が非常に大きい場合、カウントVectorのサイズが大きくなりすぎてメモリを大量に消費する可能性があるため、注意が必要です。また、このアルゴリズムは入力Vectorの要素が非負の整数であることを前提としています。この前提が満たされない場合、別のソートアルゴリズムを検討する必要があります。