A Analise Complexidade
Por: danilopalma • 26/5/2015 • Relatório de pesquisa • 1.396 Palavras (6 Páginas) • 588 Visualizações
- 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.
- Métodos de ordenação em vetores
- Bubble sort
- Selection sort
- Insertion sort
- Merge sort
- Quick sort
- 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
int aux;
|
- 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.
- 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.
...