Abrir menu principal
Text document with red question mark.svg
Este artigo ou secção contém fontes no fim do texto, mas que não são citadas no corpo do artigo, o que compromete a confiabilidade das informações (desde maio de 2017). Ajude a melhorar este artigo inserindo fontes.
Bubble sort

Bubble sort animation.gif
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso
complexidade caso médio
complexidade melhor caso
complexidade de espaços pior caso 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 operações relevantes, onde representa o número de elementos do vector. No pior caso, são feitas 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ódigoEditar

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émEditar

Referências Editar

Ligações externasEditar