View
3
Download
0
Category
Preview:
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
Recommended