counting sort

counting sort について書きます。

counting sort は、一次元配列の要素がすべてゼロ以上の整数である必要があります。

元の配列が、上記の条件を満たしていなくても、すべての要素の関係を崩さず、ゼロ以上の整数にできるならcounting sort を使えます。

計算量

O(n)

 

データ構造

ソート前に配列

counter配列　（サイズは要素が取り得る最大値長）

ソート後の配列

アルゴリズム　

  1. counter[i] = 0に初期化　
  2. counter[i]++; ( i = 元の配列[ j]  j=0,1,.....size-1 )
  3. counter[i] をcounter[0]~counter[i]までの累積和にする。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　counter[i]は0~iまでの数字が何個あるか表すことになる。　counter[i] -1 がソート後の i のインデックスとなる。
  4. ソート後の配列 [ conter[ ソート前の配列[ i ] ] -1 ] = ソート前の配列[ i ]                                                              counter[ソート前の配列 [ i ] ]--;
#include<iostream>
#include<fstream>
#include<vector>
#define max 100
using namespace std;
int main() {
    int size;
    cin>>size;
    vector<int> before(size);
    for(int i=0;i<size;i++){
        cin>>before[i];
    }
    cout << "Array before sorting:" << endl;
    for (int i = 0; i < before.size(); i++) {
        if (i)cout << " ";
        cout << before[i];
    }
    int counter[max] = {0};
    vector<int> after(before.size());
    for (int i = 0; i < before.size(); i++) {
        counter[before[i]]++;
    }
    for (int i = 0; i < max-1; i++) {
        counter[i + 1] += counter[i];
    }
    for (int i = 0; i < before.size(); i++) {
        after[counter[before[i]] - 1] = before[i];
        counter[before[i]]--;
    }
    cout << endl << endl << "Array after sorting: " << endl;
    for (int i = 0; i < after.size(); i++) {
        if (i)cout << " ";
        cout << after[i];
    }

}