兄貴の伝説 - hatena edition -

ソフトウェア職人を目指してます

7.4 計数ソート

配列 A,B を 1 オリジンにしないといけない理由を理解しないままコーディングし、その途中でインデックスがずれまくったために答えが合わず、無駄な時間を費やしてしまいました。また、A, B の配列のサイズを間違えていたため、Runtime Error を頻発させてしまいました。色々と申し訳ない感じに。。

#include <iostream>
#include <vector>

using namespace std;

static void inputArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i];
   }
}

static void printArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cout << ((i != 0) ? " " : "") << A[i];
  }
  cout << endl;
}

static const int NMAX = 10000;
static vector<int> C(NMAX + 1, 0);

static inline void countingSort(int A[], int B[], int num) {
  for (int i = 0; i < num; i++) {
    C[A[i + 1]]++;
  }
  for (int i = 1; i <= NMAX; i++) {
    C[i] = C[i] + C[i - 1];
  }
// 前から検索すると安定ソートにはならない
// for (int i = 1; i <= num; i++) {
  for (int i = num; i > 0; i--) {
    B[C[A[i]]] = A[i];
    C[A[i]]--;
  }
}  

static vector<int> A(2000000 + 1), B(2000000 + 1);

int main() {
  int n;
  cin >> n;

  inputArray(&A[1], n);

  countingSort(&A[0], &B[0], n);

  printArray(&B[1], n);
    
  return 0;
}