Root at 16:56, 27 May 2005

2005-05-27T16:56:22Z

← Older revision		Revision as of 16:56, 27 May 2005
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];

Root at 16:54, 27 May 2005

2005-05-27T16:54:55Z

New page

== 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?

Counting Sort - Revision history

Root at 16:56, 27 May 2005

Root at 16:54, 27 May 2005