of 51 /51
Counting Sort Análise de Algoritmos Nome: Andrew Gama Nome: Rony Conde

Couting Sort

Embed Size (px)

DESCRIPTION

Funcionamento do Algoritmo Couting Sort

Text of Couting Sort

Counting SortAnlise de AlgoritmosNome: Andrew GamaNome: Rony CondeCounting SortFuncionamento:

A ordenao por contagem pressupe que cada um dos n elementos do vetor de entrada um inteiro entre 1 e k (onde k representa o maior inteiro presente no vetor).

A idia bsica determinar, para cada elemento de entrada x, o numero de elementos menores ou iguais a x. Com essa informao possvel determinar exatamente onde o elemento x ser inserido.Counting SortAspectos Positivos:

Ordena vetores em tempo linear para o tamanho do vetor inicial;No realiza comparaes; um algoritmo de ordenao estvel;Aspecto Negativo:

Necessita de dois vetores adicionais para sua execuo, utilizando, assim, mais espao na memria. Counting SortComplexidade:

O algoritmo no faz comparaes entre elementos de A!Sua complexidade deve ser medida em funo do nmero das outras operaes, aritmticas, atribuies, etc.Claramente, a complexidade de COUNTING-SORT :

O(n + k). Quando k O(n), ele tem complexidade O(n).02102424012345670123401234567Array AArray CArray BCounting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for CountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for 0210242401234567000000123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for Inicializar valores do Vetor C em 0.ACB0210242401234567100000123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for Realizar Contagem do numero de cada elemento do intervalo do Vetor AACB0210242401234567100100123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Contagem do numero de cada elemento do intervalo do Vetor A0210242401234567200100123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Contagem do numero de cada elemento do intervalo do Vetor A0210242401234567210100123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Contagem do numero de cada elemento do intervalo do Vetor A0210242401234567210200123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Contagem do numero de cada elemento do intervalo do Vetor A0210242401234567210210123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Contagem do numero de cada elemento do intervalo do Vetor A0210242401234567210220123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Contagem do numero de cada elemento do intervalo do Vetor A0210242401234567210320123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Contagem do numero de cada elemento do intervalo do Vetor A0210242401234567210320123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACB0210242401234567210320123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for Realizar Complementos de casa de cada valor no Vetor CACB0210242401234567230320123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Complementos de casa de cada valor no Vetor C0210242401234567230320123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Complementos de casa de cada valor no Vetor C0210242401234567230620123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Complementos de casa de cada valor no Vetor C0210242401234567230620123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Complementos de casa de cada valor no Vetor C0210242401234567236620123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Complementos de casa de cada valor no Vetor C0210242401234567236620123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Complementos de casa de cada valor no Vetor C0210242401234567236680123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBRealizar Complementos de casa de cada valor no Vetor C0210242401234567236680123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACB02102424012345672366-180123401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for Alocar Valores no Vetor Ordenado (Vetor B)ACB0210244012345672365801234201234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)02102440123456723658-101234201234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)0210240123456723657012342401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)0210240123456723657-1012342401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)0210201234567236560123424401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)02102012345672365-160123424401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)0210012345672364601234224401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACB02100123456723-164601234224401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)0200123456722646012341224401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)020012345672-12646012341224401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)0201234567126460123401224401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)02012345671264-160123401224401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)0012345671263601234021224401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)0012345671-1263601234021224401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)0123456702636012340021224401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACBAlocar Valores no Vetor Ordenado (Vetor B)0123456702636012340021224401234567Counting SortCountingSort (A, B, k)for i 0 to k doC[i] 0;end for

for i 0 to k doC[A[j]] C[A[j]]+1;end for

for i 0 to k doC[i] C[i]+C[i-1]; end for

for j n downto 1 do B[C[A[j]]] A[j]; C[A[j]] C[A[j]]-1; end for ACB0012345670263601234021224401234567ACBCounting SortPassar Contedo do Vetor B, para o Original (Vetor A)0001234567026360123421224401234567Counting SortACBPassar Contedo do Vetor B, para o Original (Vetor A)0010123456702636012342224401234567Counting SortACBPassar Contedo do Vetor B, para o Original (Vetor A)0021012345670263601234224401234567Counting SortACBPassar Contedo do Vetor B, para o Original (Vetor A)0021201234567026360123424401234567Counting SortACBPassar Contedo do Vetor B, para o Original (Vetor A)0021220123456702636012344401234567Counting SortACBPassar Contedo do Vetor B, para o Original (Vetor A)0021224012345670263601234401234567Counting SortACBPassar Contedo do Vetor B, para o Original (Vetor A)0021224401234567026360123401234567Counting SortACBPassar Contedo do Vetor B, para o Original (Vetor A)0021224401234567026360123401234567Counting SortACBPassar Contedo do Vetor B, para o Original (Vetor A)Implementao Counting Sort