Bubble sort: diferenças entre revisões
Linha 1: | Linha 1: | ||
BEM-VINDO AO INFERNO |
|||
{{sem-fontes|data=Agosto de 2013}} |
{{sem-fontes|data=Agosto de 2013}} |
||
{{Info/Algoritmo |
{{Info/Algoritmo |
||
Linha 33: | Linha 35: | ||
8. V[j+1] = aux |
8. V[j+1] = aux |
||
9. j = j+1 |
9. j = j+1 |
||
10. k = k-1 |
10. k = k-1 |
||
</pre> |
</pre> |
||
Revisão das 18h42min de 7 de outubro de 2013
BEM-VINDO AO INFERNO
Este artigo não cita fontes confiáveis. (Agosto de 2013) |
O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vector diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequê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.
No melhor caso, o algoritmo executa operações relevantes, onde n representa o número de elementos do vector. No pior caso, são feitas operações. A complexidade desse algoritmo é de Ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.
Algoritmo
Pseudo-código
O algoritmo abaixo, descrito em pseudo-código, promete ordenar um vetor V[1..n] em ordem crescente.
Algoritmo Bubble(V, n) 1. k = n-1 2. para i = 1 até n faça 3. j = 1 4. enquanto j <= k faça 5. se V[j] > V[j+1] então 6. aux = V[j] 7. V[j] = V[j+1] 8. V[j+1] = aux 9. j = j+1 10. k = k-1
Análise do consumo de tempo
Linha | Número de execuções da linha |
---|---|
1 | 1 |
2 | n+1 |
3 | n |
4 | n |
5 | sum_{i=1}^{n} n-i+1 = (n^2 + n)/2 + 1 |
6 | <= sum_{i=1}^{n} n-i = (n^2 + n)/2 |
7 | <= sum_{i=1}^{n} n-i = (n^2 + n)/2 |
8 | <= sum_{i=1}^{n} n-i = (n^2 + n)/2 |
9 | sum_{i=1}^{n} n-i = (n^2 + n)/2 |
10 | n |
Total | <= (5/2)n^2 + (13/2)n + 3 |
O consumo de tempo de Bubble é Θ(n^2).