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

Exemplos de código

Ordenando maiores para o final na Linguagem C++:

 1 void BubbleSort(int vetor[], int tam) {
 2     for (int fim = tam-1; fim > 0; --fim) {
 3         for (int i = 0; i < fim; ++i) {
 4             if (vetor[i] > vetor[i+1]) {
 5                 int aux = vetor[i];
 6                 vetor[i] = vetor[i+1];
 7                 vetor[i+1] = aux;
 8             }
 9         }
10     }
11 }

Ordenando para maiores em Swift:

 1 func bubbleSort<T:Comparable>(_ input:[T]) -> [T] {
 2     var items       : [T] = input
 3     let itemsCount  : Int = items.count
 4     var swaped      : Bool = true
 5     
 6     repeat {
 7         swaped  = false
 8         for index in 0 ..< itemsCount - 1 {
 9             let indexToCompare = index + 1
10             if items[index] > items[indexToCompare] {
11                 swap(&items[index], &items[indexToCompare])
12                 swaped = true
13             }
14         }
15     } while swaped
16     
17     return items
18 }
19 
20 //Exemplo de uso
21 bubbleSort([6,5,4,3,2,1])  //output: [1,2,3,4,5,6]

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
• CS