fork download 
  1. #include <iostream>
  2. #include <cassert>
  3. #include <cstdio>
  4.  
  5. using namespace std;
  6. const int N = 1e7 + 5;
  7. int Len, a[N];
  8. int B[N], C[N], res[N];
  9. /**
  10.     C[]: temparary storage array
  11.     res[]: store result array,
  12.  */
  13. int cntPos, pos[N], cntNeg, neg[N];
  14.  
  15. void input() {
  16.     assert(freopen("CountingSort.inp", "r", stdin)); /// read your own input
  17.     cin >> Len;
  18.     for (int i = 1; i <= Len; i ++) {
  19.         cin >> a[i];
  20.         if (a[i] < 0) {
  21.             ++ cntNeg;
  22.             neg[cntNeg] = a[i];
  23.         } else {
  24.             ++ cntPos;
  25.             pos[cntPos] = a[i];
  26.         }
  27.     }
  28. }
  29. void cntSort(int A[], int n) {
  30.     int K = -1;
  31.     for (int i = 1; i <= n; i ++)
  32.         K = max(K, A[i]);
  33.     for (int i = 0; i <= K; i ++)
  34.         C[i] = 0;
  35.     for (int i = 1; i <= n; i ++)
  36.         ++ C[A[i]];
  37.     for (int i = 1; i <= K; i ++)
  38.         C[i] += C[i - 1];
  39.     for (int j = n; j >= 1; j --) {
  40.         B[C[A[j]]] = A[j];
  41.         -- C[A[j]];
  42.     }
  43. }
  44. void cntNegSort(int A[], int n) { /// case negative array
  45.     for (int i = 1; i <= n; i ++)
  46.         A[i] = -A[i];
  47.     cntSort(A, n);
  48.     for (int i = 1; i <= cntNeg; i ++) {
  49.         res[i] = -B[cntNeg - i + 1];
  50.     }
  51. }
  52. void cntPosSort(int A[], int n) { /// case Positive array
  53.     cntSort(A, n);
  54.     for (int i = 1; i <= cntPos; i ++)
  55.         res[i + cntNeg] = B[i];
  56. }
  57. void output(int A[], int n) {
  58.     cout << n << endl;
  59.     for (int i = 1; i <= n; i ++)
  60.         cout << A[i] << " ";
  61. }
  62. int main() {
  63.     input();
  64.     if (cntNeg != 0)
  65.         cntNegSort(neg, cntNeg);
  66.     if (cntPos != 0)
  67.     cntPosSort(pos, cntPos);
  68.     output(res, Len);
  69.     return 0;
  70. }
  71.  
Runtime error #stdin #stdout #stderr 0s 237760KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
prog: prog.cpp:16: void input(): Assertion `freopen("CountingSort.inp", "r", stdin)' failed.
https://ideone.com/NVan54
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!