Bubble sort

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

Introdução

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, decrito 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ç234234a
3.         j = 1$%
4.         enquanto j <= k faça
5.             se V[j] > V[j+1] então
6.                 aux = V[j]3423
7.                 V[j] = V[j+1]
8.                 V[j+1] = aux
9.             j = j+1

Código em C

void BubbleSort(int vetor[], int tamanho)
{
	int aux, i, j;
	
	for(j=tamanho-1; j>=1; j--)
        {
		for(i=0; i<j; i++)
                {
			if(vetor[i]>vetor[i+1])
                        {
				aux=vetor[i];
                                vetor[i]=vetor[i+1];
                                vetor[i+1]=aux;
                        }
                }
        }
}

Demonstração de corretude

A demonstração do algoritmo se apóia nos seguintes invariantes, provados por indução matemática:

• (i0): na linha 2, V[n-i+2 .. n] é crescente.

Prova: no momento da entrada do laço externo, quando i=1, o invariante vale, já que V[n+1 .. n] é vazio e, portanto, crescente. Suponha agora que o invariante vale se trocarmos i por i-1. Queremos mostrar que ele também vale para i. Por hipótese de indução, V[n-i+3 .. n] é crescente. Pelo invariante (i1), ao terminar o laço das linhas 4-9, teremos que V[1 .. n-i] <= V[n-i+1]. V[n-i+2] <= V[n-i+3 .. n]. Assim, V[n-i+2 .. n] é crescente.

Observe que a validade de (i0) em conjunto com a condição de parada do algoritmo (i = n+1) implicam na corretude do mesmo: V[n-(n+1)+2 .. n] = V[1 .. n] é crescente.

• (i1): na linha 4, vale que V[ j ] >= V[1 .. j-1]

Prova: o invariante vale na entrada do laço das linhas 4-9, quando j=1, pois V[1] >= V[1..0] (vazio). Suponha agora que o invariante vale se trocarmos j por j-1. Então, V[ j-1 ] >= V[1 .. j-2] na linha 4. Ora, mas podemos ver que, ao final do laço interno, V[ j ] >= V[ j-1 ]. De fato, na linha 5, se V[ j-1 ] > V[ (j-1)+1 ] = V[ j ], trocaremos V[ j-1 ] e V[ j ] de posição, o que garante que V[ j ] >= V[ j-1 ] sob qualquer circunstância.

Observe que, ao final do laço interno, V[n-i+1] >= V[1 .. n-i]: aplique (i1) com j = k+1, notando que k = n-i.

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 é \theta(n^2).

TODO: provar.

Versão alternativa

• Abaixo há um algoritmo Bubble Sort onde a implementação é a mais simples possível, ou seja, é a versão original do Bubble Sort sem o aprimoramento da variável "houve troca".

BUBBLESORT (V[], n)
    houveTroca <- verdade                       # uma variável de controle
    enquanto houveTroca for verdade faça:
        houveTroca <- falso
        para i de 1 até n-1 faça:
              se V[i] vem depois de V[i + 1]
                   então troque V[i] e V[i + 1] de lugar e
                   houveTroca <- verdade


              Para j de 1 até (i - 1) Passo 1
                   Se a[j - 1] > a[j] Então
			aux <- a[j]
			a[j] <- a[j - 1]
			a[j - 1] <- aux
			FimSe

• Observação: Neste algoritmo tanto o melhor caso, como o pior caso tem ordem "n²", porque em ambos os casos os ciclos são sempre realizados até ao fim, mesmo quando os elementos já estão ordenados.

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]