Bubble sort

BEM-VINDO AO INFERNO

Bubble sort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	$O(n^{2})$
complexidade caso médio	$O(n^{2})$
complexidade melhor caso	$O(n)$
complexidade de espaços pior caso	$O(1)$ auxiliar
Algoritmos

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 $n$ operações relevantes, onde n representa o número de elementos do vector. No pior caso, são feitas $n^{2}$ 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).

Fluxograma

Ver também

• Ordenação de vector
• Quick sort
• Heapsort
• Merge sort
• Selection sort
• Pesquisa binária

Ligações externas

• C2.com
• CS
• Veja também um algoritmo bubble sort oscilante em C
• Bubble Código de classificação
• [1]
• Simulador online do Bublesort
• Exemplo de Bubble-Sort com "Dança"
• Sou Computeiro
• [2]