Bubble sort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde Agosto de 2013).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.
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 animation.gif

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[editar | editar código-fonte]

Bubblesort.png

Implementação[editar | editar código-fonte]

Exemplo em Linguagem C:

void bubble_sort(int vetor[], int tamanho) {
    int comparacoes = 0;
    int trocas = 0;
 
    for(int i=tamanho-1; i >= 1; i--) {
        for(int j=0; j < i ; j++) {
            comparacoes ++;
            if(vetor[j]>vetor[j+1]) {
                 aux = vetor[j];
                 vetor[j] = vetor[j+1];
                 vetor[j+1] = aux;
                 trocas++;
            }
        }
    }
}

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]