A Analise Complexidade

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.

2. 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

void bolha(int vet[10], int tl) { int aux;     for(int i=0;i       {       for(int j=i+1;j          {          if(vet[j]             {             aux = vet[i];             vet[i] = vet[j];             vet[j] = aux;             }          }      } }

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]

5

15

45

35

25

[pic 17]

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

5

15

35[pic 20]

45

25

   0            1             2             3              4           [pic 21][pic 22][pic 23]

5

15

25

45

35

[pic 24]

   0            1             2             3              4          

5

15

25

35

45

Aqui se tem um algoritmo que certamente funciona.  Porém, a que preço? O algoritmo faz muitas comparações desnecessárias e, além disso, troca somente com o seu vizinho.

1. Análise e tempo de processamento do Bubble sort

Complexidade algorítmica que ocorrem quando os itens de dados são processados aos pares, muitas vezes em uma repetição dentro da outra.