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

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, e a cada passagem fazer 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.

Pseudocódigo

Este algoritmo percorre a lista de itens ordenáveis do início ao fim, verificando a ordem dos elementos dois a dois, e trocando-os de lugar se necessário. Percorre-se a lista até que nenhum elemento tenha sido trocado de lugar na passagem anterior.

procedure bubbleSort( A : lista de itens ordenaveis ) defined as:
  do
    trocado := false
    for each i in 0 to length( A ) - 2 do:
      // verificar se os elementos estão na ordem certa
      if A[ i ] > A[ i + 1 ] then
        // trocar elementos de lugar
        trocar( A[ i ], A[ i + 1 ] )
        trocado := true
      end if
    end for
  // enquanto houver elementos sendo reordenados.
  while trocado
end procedure

C

void bubbleSort(int* vet, int length) {
	int i, j, temp;

	for (i = 0; i < length - 1; i++){
             for (j = (i+1); j < length; j++){
                  if (vet[j] < vet[i]){
                       temp = vet[i];
                       vet[i] = vet[j];
                       vet[j] = temp;
                  }
              }
        }
}

Java

 0    void bubbleSort(int arr[]) 
 1     { 
 2         int n = arr.length; 
 3         for (int i = 0; i < n-1; i++) 
 4             for (int j = 0; j < n-i-1; j++) 
 5                 if (arr[j] > arr[j+1]) 
 6                 { 
 7                     // swap temp and arr[i] 
 8                     int temp = arr[j]; 
 9                     arr[j] = arr[j+1]; 
10                     arr[j+1] = temp; 
11                 } 
12     }

Ver também

• Algoritmo de ordenação
• Quick sort
• Heapsort
• Merge sort
• Selection sort
• Pesquisa binária

Referências 

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 2ed. MIT Press e McGraw-Hill, 2001. ISBN 0-262-03293-7. Problem 2-2, pg.40.
• Sorting in the Presence of Branch Prediction and Caches
• Fundamentals of Data Structures by Ellis Horowitz, Sartaj Sahni and Susan Anderson-Freed ISBN 81-7371-605-6

Ligações externas

• Implementação do algoritmo em várias linguagens de programação
• C2.com