Fedora
2156 palavras
9 páginas
07/03/2013Estrutura de Dados Prof. Dr. Antonio Marcos SELMINI profselmini@uninove.br Algoritmo de ordenação por troca (método bolha – bubble sort)
1
Bacharelado em Sistemas de Informação Estrutura de Dados – Noções sobre Complexidade de Algoritmos Prof. Dr. Antonio Marcos SELMINI – profselmini@uninove.br
Algoritmo de ordenação por troca
Há situações em que é necessário ordenar dados. Para esse procedimento existem algoritmos de ordenação; O método de ordenação mais simples é o de ordenação por trocas, também chamado de método bolha ou bubble sort; Este algoritmo de ordenação efetua comparações entre os dados armazenados em um vetor de tamanho n. Cada elemento de posição i será comparado com o elemento de posição i + 1, e quando estiver fora do lugar, a troca deverá ser feita;
2
1
07/03/2013
Bacharelado em Sistemas de Informação Estrutura de Dados – Noções sobre Complexidade de Algoritmos Prof. Dr. Antonio Marcos SELMINI – profselmini@uninove.br
Simulação do algoritmo
Considere a simulação para um vetor de 5 posições – 1ª execução:
0 5 0 4 0 4 0 4 0 4 1 4 1 5 1 3 1 3 1 3 2 3 2 3 2 5 2 2 2 2 3 2 3 2 3 2 3 5 3 1 4 1 4 1 4 1 4 1 4 5
3
5 > 4? Troca! Após percorrer todo o vetor, os elementos estão ordenados? NÃO!! Solução? Executar todo o processo novamente!!
5 > 3? Troca!
5 > 2? Troca!
5 > 1? Troca!
Bacharelado em Sistemas de Informação Estrutura de Dados – Noções sobre Complexidade de Algoritmos Prof. Dr. Antonio Marcos SELMINI – profselmini@uninove.br
Simulação do algoritmo
Considere a simulação para um vetor de 5 posições – 2ª execução
0 4 0 3 0 3 0 3 1 3 1 4 1 2 1 2 2 2 2 2 2 4 2 1 3 1 3 1 3 1 3 4 4 5 4 5 4 5 4 5 4 > 5? Não há troca!!
4
4 > 3? Troca!
4 > 2? Troca!
4 > 1? Troca!
Após percorrer novamente todo o vetor, os elementos estão ordenados? NÃO!! Solução? Executar todo o processo novamente!!
2
07/03/2013
Bacharelado em Sistemas de Informação Estrutura de Dados – Noções sobre