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

Bubble sort cor editada

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.

Fluxograma

Implementação

Exemplo em Linguagem C:

  #include <stdio.h>
  int main(void){
 
  int vetor[10] = {10,9,8,7,6,5,4,3,2,1};
 
  int tamanho = 10;
  int aux;
 
  for(int i=tamanho-1; i >= 1; i--) {  
 
    for( int j=0; j < i ; j++) {
 
      if(vetor[j]>vetor[j+1]) {
 
        aux = vetor[j];
        vetor[j] = vetor[j+1];
        vetor[j+1] = aux;
 
        }
      }
    }
 
  for( int r = 0; r < 10; ++r){
 
    printf("%d\n",vetor[r]);
 }
}

Exemplo em Linguagem Java:

class BubbleSort {
    public static void main(String args[]) {
 
        int vetor[] = {10,9,8,7,6,5,4,3,2,1};
        boolean troca = true;
        int aux;
        while (troca) {
            troca = false;
            for (int i = 0; i < vetor.length - 1; i++) {
                if (vetor[i] > vetor[i + 1]) {
                    aux = vetor[i];
                    vetor[i] = vetor[i + 1];
                    vetor[i + 1] = aux;
                    troca = true;
                }
            }
        }
    }
}

Ver também

• Ordenação de vector
• Quick sort
• Heapsort
• Merge sort
• Selection sort
• Pesquisa binária

Ligações externas

• Implementação do algoritmo em várias linguagens de programação
• C2.com
• CS
• Bubble Código de classificação
• Simulador online do Bublesort
• Exemplo de Bubble-Sort com "Dança"
• [1]