Algoritmo Counting Sort
2258 palavras
10 páginas
ALGORITMOCOUNTING SORT
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
• Funcionamento:
• A ordenação por contagem pressupõe que cada um dos n elementos do vetor de entrada é um inteiro entre 1 e k (k representa o maior inteiro presente no vetor).
• A ideia 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.
SIMULAÇÃO
VETOR =
0
1
2
3
4
5
6
7
1
8
3
4
6
7
2
5
0
1
2
3
4
5
6
7
8
AUX =
0
RESPOSTA=
1
2
3
4
5
6
7
SIMULAÇÃO
VETOR =
AUX =
0
1
2
3
4
5
6
7
1
8
3
4
6
7
2
5
0
1
2
3
4
5
6
7
8
0
0
0
0
0
0
0
0
0
0
RESPOSTA=
1
2
3
4
5
6
7
SIMULAÇÃO
VETOR =
AUX =
0
1
2
3
4
5
6
7
1
8
3
4
6
7
2
5
0
1
2
3
4
5
6
7
8
0
0
0
0
0
0
0
0
0
0
RESPOSTA=
1
2
3
4
5
6
7
SIMULAÇÃO
VETOR =
AUX =
0
1
2
3
4
5
6
7
1
8
3
4
6
7
2
5
0
1
2
3
4
5
6
7
8
0
1
0
0
0
0
0
0
0
0
RESPOSTA=
1
2
3
4
5
6
7
SIMULAÇÃO
VETOR =
AUX =
0
1
2
3
4
5
6
7
1
8
3
4
6
7
2
5
0
1
2
3
4
5
6
7
8
0
1
0
0
0
0
0
0
0
0
RESPOSTA=
1
2
3
4
5
6
7
SIMULAÇÃO
VETOR =
AUX =