- Comparados
- Trocados
- No lugar
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
- 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.
- 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.
- 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