TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

A Analise Complexidade

Por:   •  26/5/2015  •  Relatório de pesquisa  •  1.396 Palavras (6 Páginas)  •  201 Visualizações

Página 1 de 6
  1. Métodos de ordenação

Algoritmo de ordenação em ciência da computação é um algoritmo que coloca os elementos de uma dada seqüência em certa ordem, em outras palavras, efetua sua ordenação completa ou parcial. A ordem mais usada é a numérica (crescente). Existem várias razões para se ordenar uma seqüência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente.

Ordenar é uma operação fundamental em computação e por causa disto inúmeros bons algoritmos foram desenvolvidos. Qual o melhor algoritmo? Como muitas outras vezes esta resposta depende de vários fatores. Depende, por exemplo, do número de itens a serem ordenados, se os números já estão mais ou menos ordenados e outros.

  1. Métodos de ordenação em vetores

  1. Bubble sort
  2. Selection sort
  3. Insertion sort
  4. Merge sort
  5. Quick sort

  1. Bubble sort - Método da Bolha

A ordenação por troca é o método mais básico de ordenação. O algoritmo da bolha, ou em Inglês, Bubble sort, ou ordenação por flutuação. A idéia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o menor elemento da seqüência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.

Este método compara todos os elementos do vetor, dois a dois, do primeiro ao último. Efetua a ordenação através de trocas entre pares de números sucessivos (trocando-os de posição entre si) se necessário, para que o segundo (J) seja o maior e o primeiro seja o menor (I). Como conseqüência, o menor elemento ficará na primeira casa mais a esquerda do vetor. Este elemento é desconsiderado no próximo passo.

Vamos assumir que os números a serem ordenados estão armazenados num vetor. A cada passo cada elemento do vetor é comparado com seu sucessor, sendo os 2 trocados de posição caso estejam "fora de ordem", ou seja, o segundo menor do que o primeiro.

Consiste em dois laços encadeados. Para facilitar considere os laços como laço i e laço j. O laço j é o interno e ele passa por cada item da tabela (da segunda posição até o fim). Comparando o elemento da posição (j) com o anterior (i). Caso seja maior que o anterior (da posição i), estes dois elementos são trocados. Após j ter passado por toda a tabela, ele volta ao inicio i é incrementado. Este processo é repetido até que todo o vetor esteja ordenado.


Implementação do Bubble sort em C

  1. void bolha(int vet[10], int tl)
  2. {

int aux;

  1.     for(int i=0;i
  2.       {
  3.       for(int j=i+1;j
  4.          {
  5.          if(vet[j]
  6.             {
  7.             aux = vet[i];
  8.             vet[i] = vet[j];
  9.             vet[j] = aux;
  10.             }
  11.          }
  12.      }
  13. }
  1. Representação gráfica do Bubble sort

    0            1             2             3              4           [pic 1][pic 2][pic 3]

35

45

15

5

25

[pic 4]

    0            1             2             3              4           [pic 5][pic 6]

15

45

35

5

25

[pic 7][pic 8]

    0            1             2             3              4           [pic 9][pic 10]

5

45

35

15

25

[pic 11]

    0            1             2             3              4           [pic 12][pic 13]

5

35

45

15

25

[pic 14]

    0            1             2             3              4           [pic 15][pic 16]

...

Baixar como (para membros premium)  txt (5.2 Kb)   pdf (156.3 Kb)   docx (23.8 Kb)  
Continuar por mais 5 páginas »
Disponível apenas no TrabalhosGratuitos.com