Embed Size (px)
DESCRIPTION
Funcionamento do Algoritmo Couting Sort
Citation preview
Counting Sort
Análise de Algoritmos
Nome: Andrew GamaNome: Rony Conde
Counting Sort Funcionamento:
A ordenação por contagem pressupõe 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 idéia básica é determinar, para cada elemento de entrada x,
o numero de elementos menores ou iguais a x. Com essa
informação é possível determinar exatamente onde o
elemento x será inserido.
Counting Sort Aspectos Positivos:
Ordena vetores em tempo linear para o tamanho do vetor inicial;
Não realiza comparações; É um algoritmo de ordenação estável;
Aspecto Negativo:
Necessita de dois vetores adicionais para sua execução, utilizando, assim, mais espaço na memória.
Counting Sort Complexidade:
O algoritmo não faz comparações entre elementos de A! Sua complexidade deve ser medida em função do número
das outras operações, aritméticas, atribuições, etc. Claramente, a complexidade de COUNTING-SORT é:
O(n + k). Quando k O(n), ele tem complexidade O(n).∈
0 2 10 2 4 240 1 2 3 4 5 6 7
0 1 2 3 4
0 1 2 3 4 5 6 7
Array A
Array C
Array B
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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 do
C[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
0 2 10 2 4 240 1 2 3 4 5 6 7
0 0 00 00 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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.
A
C
B
0 2 10 2 4 240 1 2 3 4 5 6 7
1 0 00 00 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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 A
A
C
B
0 2 10 2 4 240 1 2 3 4 5 6 7
1 0 01 00 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Contagem do numero de cada elemento do intervalo do Vetor A
0 2 10 2 4 240 1 2 3 4 5 6 7
2 0 01 00 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Contagem do numero de cada elemento do intervalo do Vetor A
0 2 10 2 4 240 1 2 3 4 5 6 7
2 1 01 00 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Contagem do numero de cada elemento do intervalo do Vetor A
0 2 10 2 4 240 1 2 3 4 5 6 7
2 1 02 00 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Contagem do numero de cada elemento do intervalo do Vetor A
0 2 10 2 4 240 1 2 3 4 5 6 7
2 1 02 10 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Contagem do numero de cada elemento do intervalo do Vetor A
0 2 10 2 4 240 1 2 3 4 5 6 7
2 1 02 20 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Contagem do numero de cada elemento do intervalo do Vetor A
0 2 10 2 4 240 1 2 3 4 5 6 7
2 1 03 20 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Contagem do numero de cada elemento do intervalo do Vetor A
0 2 10 2 4 240 1 2 3 4 5 6 7
2 1 03 20 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
0 2 10 2 4 240 1 2 3 4 5 6 7
2 1 03 20 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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 C
A
C
B
0 2 10 2 4 240 1 2 3 4 5 6 7
2 3 03 20 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Complementos de casa de cada valor no Vetor C
0 2 10 2 4 240 1 2 3 4 5 6 7
2 3 03 20 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Complementos de casa de cada valor no Vetor C
0 2 10 2 4 240 1 2 3 4 5 6 7
2 3 06 20 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Complementos de casa de cada valor no Vetor C
0 2 10 2 4 240 1 2 3 4 5 6 7
2 3 06 20 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Complementos de casa de cada valor no Vetor C
0 2 10 2 4 240 1 2 3 4 5 6 7
2 3 66 20 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Complementos de casa de cada valor no Vetor C
0 2 10 2 4 240 1 2 3 4 5 6 7
2 3 66 20 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Complementos de casa de cada valor no Vetor C
0 2 10 2 4 240 1 2 3 4 5 6 7
2 3 66 80 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Realizar Complementos de casa de cada valor no Vetor C
0 2 10 2 4 240 1 2 3 4 5 6 7
2 3 66 80 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
0 2 10 2 4 240 1 2 3 4 5 6 7
2 3 66-1 80 1 2 3 4
0 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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)
A
C
B
0 2 10 2 4 40 1 2 3 4 5 6 7
2 3 65 80 1 2 3 4
20 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
0 2 10 2 4 40 1 2 3 4 5 6 7
2 3 65 8-10 1 2 3 4
20 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
0 2 10 2 40 1 2 3 4 5 6 7
2 3 65 70 1 2 3 4
2 40 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
0 2 10 2 40 1 2 3 4 5 6 7
2 3 65 7-10 1 2 3 4
2 40 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
0 2 10 20 1 2 3 4 5 6 7
2 3 65 60 1 2 3 4
2 440 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
0 2 10 20 1 2 3 4 5 6 7
2 3 65-1 60 1 2 3 4
2 440 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
0 2 100 1 2 3 4 5 6 7
2 3 64 60 1 2 3 4
2 2 440 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
0 2 100 1 2 3 4 5 6 7
2 3-1 64 60 1 2 3 4
2 2 440 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
0 2 00 1 2 3 4 5 6 7
2 2 64 60 1 2 3 4
1 2 2 440 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
0 2 00 1 2 3 4 5 6 7
2-1 2 64 60 1 2 3 4
1 2 2 440 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
0 20 1 2 3 4 5 6 7
1 2 64 60 1 2 3 4
0 1 2 2 440 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
0 20 1 2 3 4 5 6 7
1 2 64-1 60 1 2 3 4
0 1 2 2 440 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
00 1 2 3 4 5 6 7
1 2 63 60 1 2 3 4
0 21 2 2 440 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
00 1 2 3 4 5 6 7
1-1 2 63 60 1 2 3 4
0 21 2 2 440 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
0 1 2 3 4 5 6 7
0 2 63 60 1 2 3 4
0 0 21 2 2 440 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
Alocar Valores no Vetor Ordenado (Vetor B)
0 1 2 3 4 5 6 7
0 2 63 60 1 2 3 4
0 0 21 2 2 440 1 2 3 4 5 6 7
Counting SortCountingSort (A, B, k)for i 0 to k do
C[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
A
C
B
00 1 2 3 4 5 6 7
0 2 63 60 1 2 3 4
0 21 2 2 440 1 2 3 4 5 6 7
A
C
B
Counting Sort
Passar Conteúdo do Vetor B, para o Original (Vetor A)
0 00 1 2 3 4 5 6 7
0 2 63 60 1 2 3 4
21 2 2 440 1 2 3 4 5 6 7
Counting Sort
A
C
B
Passar Conteúdo do Vetor B, para o Original (Vetor A)
0 0 10 1 2 3 4 5 6 7
0 2 63 60 1 2 3 4
2 2 2 440 1 2 3 4 5 6 7
Counting Sort
A
C
B
Passar Conteúdo do Vetor B, para o Original (Vetor A)
0 0 210 1 2 3 4 5 6 7
0 2 63 60 1 2 3 4
2 2 440 1 2 3 4 5 6 7
Counting Sort
A
C
B
Passar Conteúdo do Vetor B, para o Original (Vetor A)
0 0 21 20 1 2 3 4 5 6 7
0 2 63 60 1 2 3 4
2 440 1 2 3 4 5 6 7
Counting Sort
A
C
B
Passar Conteúdo do Vetor B, para o Original (Vetor A)
0 0 21 2 20 1 2 3 4 5 6 7
0 2 63 60 1 2 3 4
440 1 2 3 4 5 6 7
Counting Sort
A
C
B
Passar Conteúdo do Vetor B, para o Original (Vetor A)
0 0 21 2 2 40 1 2 3 4 5 6 7
0 2 63 60 1 2 3 4
40 1 2 3 4 5 6 7
Counting Sort
A
C
B
Passar Conteúdo do Vetor B, para o Original (Vetor A)
0 0 21 2 2 440 1 2 3 4 5 6 7
0 2 63 60 1 2 3 4
0 1 2 3 4 5 6 7
Counting Sort
A
C
B
Passar Conteúdo do Vetor B, para o Original (Vetor A)
0 0 21 2 2 440 1 2 3 4 5 6 7
0 2 63 60 1 2 3 4
0 1 2 3 4 5 6 7
Counting Sort
A
C
B
Passar Conteúdo do Vetor B, para o Original (Vetor A)
Implementação Counting Sort
![Unidade 3: FUNÇÕES NUMÉRICAScmq.esalq.usp.br/wiki/lib/exe/fetch.php?media=biometria:r-tutor:... · [1] 1 15 18 3 6 > cumsum(b) [1] 1 16 34 37 43 > sort(b) [1] 1 3 6 15 18 > sort(b,](https://img.document.onl/doc/110x75/5f4c0d5a77b9d6270e192007/unidade-3-funes-num-1-1-15-18-3-6-cumsumb-1-1-16-34-37-43-.jpg)
![Introdução*àInformácae* Computação* · Exemplos*de*problemas*computáveis* • Ordenar*listadesordenada – Inser/on*sort*nalinguagem*Java:* public Long[] ordenarCrescente(Long[]](https://img.document.onl/doc/110x75/5c02c52909d3f2a9258b8ad7/introducaoainformacae-computacao-exemplosdeproblemascomputaveis.jpg)
