Counting Sort: Difference between revisions
From Wiki**3
No edit summary |
No edit summary |
||
| Line 9: | Line 9: | ||
* dois ciclos em M | * dois ciclos em M | ||
* três ciclos em N | * três ciclos em N | ||
Espaço adicional: O(N+M) | |||
=== Primeira versão === | === Primeira versão === | ||
void countingsort(int a[], int l, int r) { | void '''countingsort'''(int a[], int l, int r) { | ||
int i, j, cnt[M+1]; | int i, j, cnt[M+1]; | ||
int b[maxN]; | int b[maxN]; | ||
| Line 24: | Line 25: | ||
=== Segunda versão === | === Segunda versão === | ||
void countingsort(int a[], int l, int r) { | void '''countingsort'''(int a[], int l, int r) { | ||
int i, j, cnt[M]; | int i, j, cnt[M]; | ||
int b[maxN]; | int b[maxN]; | ||
Latest revision as of 16:56, 27 May 2005
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
Espaço adicional: O(N+M)
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?