【AOJ ALDS1_6】A: Counting Sort

問題

Counting Sort | Aizu Online Judge

方針

• 計数ソート（バケットソート）をしよう.
• アルゴリズムは問題をそのまま実装.

コード

#include<bits/stdc++.h>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;

int a[2000001];
int b[2000001];  
int c[2000001];

signed main(){
  int n;
  cin >> n;
  
  memset(c, 0, sizeof(c));

  rep(i,n){
    cin >> a[i+1];
    c[a[i+1]]++;
  }

  REP(i, 1, 2000001){
    c[i] += c[i-1];
  }
  
  REP(i,1,n+1){
    b[c[a[i]]] = a[i];
    c[a[i]]--;
  }

  cout << b[1];
  REP(i,2,n+1){
    cout << " " << b[i];
  }
  cout << "\n";
}