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

Uma versão em C, recursiva :

Entra: tamanho do vetor a ser organizado e vetor de números.

Saida: vetor organizado.

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 void swap(int *a, int *b){ 
 4     int temp = *a; 
 5     *a = *b; 
 6     *b = temp; 
 7 } 
 8 void bubbleSort(int *v, int n){ 
 9     if (n < 1)return; 
10  
11     for (int i=0; i<n; i++) 
12         if (v[i] > v[i+1]) 
13             swap(&v[i], &v[i+1]);  
14     bubbleSort(v, n-1); 
15 } 
16 
17 int main(){
18     int tam,i,*v;
19     scanf("%d",&tam);
20     v=(int*)malloc(tam*sizeof(int));
21     for(i=0;i<tam;i++)scanf("%d",&v[i]);
22     bubbleSort(v,tam-1);
23     for(i=0;i<tam;i++)printf("%d ",v[i]);
24     return 0;
25 }

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