Fedora

Disponível somente no TrabalhosFeitos
  • Páginas : 9 (2156 palavras )
  • Download(s) : 0
  • Publicado : 8 de março de 2013
Ler documento completo
Amostra do texto
07/03/2013

Estrutura 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 ordenardados. 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á serfeita;

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 5posiçõ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 sobreComplexidade 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 – 3ª execução:
0 3 0 2 0 2 0 2 1 2 1 3 1 1 1 1 2 1 2 1 2 3 2 3 3 4 3 4 3 4 3 4 4 5 4 5 4 5 4 5 4 > 5? Não há troca!!
5

3 > 2? Troca!

3 > 1? Troca!

3 > 4? Não há troca!!

Após percorrer novamente todo o vetor, os elementos estãoordenados? NÃO!! Solução? Executar todo o processo novamente!!

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 – 4ª execução:
0 2 0 1 0 1 0 1 1 1 1 2 1 2 1 2 2 3 2 3 2 3 2 3 3 4 3 4 3 4 3 4 4 5 4 5 4 5 4 5 4 > 5?Não há troca!!
6

2 > 1? Troca! Após percorrer novamente todo o vetor, os elementos estão ordenados? SIM!!

2 > 3? Não há troca!!

3 > 4? Não há troca!!

3

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

Algoritmo em linguagem C
#include #include #define n5 //tamanho do vetor int main() { int x[n], i, j, aux; for(i = 0; i < n; i++) { printf("Digite um valor: "); scanf("%d", &x[i]); } for(i = 0; i < n; i++) for(j = 0; j < n-1; j++) if(x[j] > x[j+1]) { aux = x[j]; x[j] = x[j+1]; x[j+1] = aux; } }

7

Bacharelado em Sistemas de Informação Estrutura de Dados – Noções sobre Complexidade de Algoritmos Prof. Dr. Antonio Marcos SELMINI –profselmini@uninove.br

Análise de complexidade
O principal trecho do programa de ordenação é aquele em que a ordenação é realizada; for(i = 0; i < n; i++) for(j = 0; j < n-1; j++) if(x[j] > x[j+1]) { aux = x[j]; x[j] = x[j+1]; x[j+1] = aux; }

8

4

07/03/2013

Bacharelado em Sistemas de Informação Estrutura de Dados – Noções sobre Complexidade de Algoritmos Prof. Dr. Antonio Marcos SELMINI –...
tracking img