View source for Counting Sort

== Introdução ==

* Estável.
* Explora o facto de as chaves estarem limitadas a um intervalo.

== Implementação ==

Complexidade: O(N+M)
* dois ciclos em M
* trÃªs ciclos em N

=== Primeira versão ===

  void countingsort(int a[], int l, int r) {
    int i, j, cnt[M+1]; 
    int b[maxN];
    for (j = 0; j <= M; j++) cnt[j] = 0;
    for (i = l; i <= r; i++) cnt[a[i]+1]++;
    for (j = 1; j <  M; j++) cnt[j] += cnt[j-1];
    for (i = l; i <= r; i++) b[cnt[a[i]]++] = a[i];
    for (i = l; i <= r; i++) a[i] = b[i];
  }

=== Segunda versão ===

  void countingsort(int a[], int l, int r) {
    int i, j, cnt[M]; 
    int b[maxN];
    for (j = 0; j <  M; j++) cnt[j] = 0;
    for (i = l; i <= r; i++) cnt[a[i]]++;
    for (j = 1; j <  M; j++) cnt[j] += cnt[j-1];
    for (i = r; i >= l; i--) b[--cnt[a[i]]] = a[i];
    for (i = l; i <= r; i++) a[i] = b[i];
  } 

Diferenças?