Comparações
Trocas
Passagem

  • Comparados
  • Trocados
  • No lugar

Mais sobre o bubble sort

Bubble sort

O bubble sort (ordenação por bolha) percorre uma lista vezes sem conta, compara cada par de vizinhos e troca-os quando o da esquerda é maior. Após cada passagem, o maior valor ainda fora do lugar subiu como uma bolha até ao fim. Reproduza a ordenação a qualquer velocidade, ou avance uma comparação de cada vez, e acompanhe os contadores de comparações, trocas e passagens. Prima Reproduzir para ver a ordenação, ou Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Os contadores mostram comparações, trocas e passagens. Escolha quantas barras, como começam, ou escreva os seus próprios números. Com o quadro selecionado, as setas avançam e recuam, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Escolha o número de barras e a ordem inicial: aleatória, quase ordenada, invertida ou com poucos valores distintos. Ou escreva os seus próprios números.
  2. Prima Reproduzir, ou use Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto da ordenação.
  3. Veja os contadores de comparações, trocas e passagens e compare-os com o pior caso.

Como funciona o bubble sort

Comece pela esquerda. Compare os dois primeiros valores; se o da esquerda for maior, troque-os. Avance uma posição para a direita e compare de novo, até ao fim da lista. Isso é uma passagem, e deixa o maior valor na última posição. A passagem seguinte para uma posição antes. Continue até uma passagem não fazer trocas, ou até restar só um valor.

Contar o trabalho

Para n valores, a primeira passagem faz n − 1 comparações, a seguinte n − 2, e assim por diante, por isso uma ordenação completa faz no máximo n(n − 1)/2 comparações. O número de trocas é sempre o número de inversões da lista inicial: pares de valores na ordem errada. Uma lista invertida tem o máximo, n(n − 1)/2. Uma lista ordenada não tem nenhuma e, com a paragem antecipada, precisa de uma só passagem de n − 1 comparações.

Perguntas frequentes

Porque se chama bubble sort?

Bubble quer dizer bolha: os valores grandes sobem até ao fim da lista como bolhas na água. Em cada passagem, o maior valor ainda fora do lugar avança passo a passo para a direita até chegar à posição final.

Quantas comparações e trocas faz o bubble sort?

No máximo n(n − 1)/2 comparações para n valores: 45 para 10 valores, 780 para 40. As trocas são sempre iguais ao número de inversões da lista inicial, desde nenhuma numa lista ordenada até n(n − 1)/2 numa invertida.

Para que serve a paragem antecipada?

Se uma passagem inteira não fizer trocas, todos os pares de vizinhos estão por ordem, por isso a lista está ordenada e a ordenação pode parar. Com a paragem antecipada ativa, uma lista ordenada precisa de uma passagem. Sem ela, o bubble sort faz sempre todas as n − 1 passagens.

O bubble sort é usado na prática?

Raramente. É simples e estável, mas demora em média um tempo proporcional a n². O insertion sort faz o mesmo com menos passos em listas pequenas ou quase ordenadas, e o merge sort ou o quicksort são muito mais rápidos em listas grandes.

Os meus números são enviados para algum lado?

Não. A ordenação corre no navegador, e as últimas definições ficam guardadas no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor