Bubble Sort

• O quê é o Bubble Sort?
• Quais são as características do Bubble Sort?
• Qual é o algoritmo do Bubble Sort?
• Qual é o desempenho do Bubble Sort?
  • Pior Caso
  • Melhor Caso
• Como implementar o Bubble Sort?

O quê é o Bubble Sort?

O Bubble Sort (Ordenação por Bolha) é um algoritmo de ordenação que funciona trocando repetidamente de posição, os elementos adjacentes em um arranjo que estão fora de ordem entre si. O algoritmo leva esse nome por “borbulhar” os maiores elementos para o final do arranjo.

O Bubble Sort apresenta um desempenho ruim, quando comparado à outros algoritmos de ordenação. No entanto, por ser de simples compreensão, é frequentemente usado para motivar o estudo de outros algoritmos de ordenação.

Quais são as características do Bubble Sort?

• O Bubble Sort é um algoritmo iterativo.
• O Bubble Sort é um algoritmo de ordenação por comparação.
• O Bubble Sort é um algoritmo de ordenação estável.
• O desempenho do algoritmo não é sensível aos dados de entrada.

Qual é o algoritmo do Bubble Sort?

1. Percorra a o arranjo de entrada, do início ao fim.
2. Para cada elemento considerado, verifique se o elemento subsequente no arranjo é menor.
3. Em caso afirmativo, troque os dois elementos de posição no arranjo.
4. Ao terminar de percorrer o arranjo, verifique se algum elemento trocou de posição. Em caso afirmativo, volte ao Passo 1.
5. O arranjo está ordenado.

Qual é o desempenho do Bubble Sort?

O Bubble Sort não é um algoritmo de ordenação indicado para a ordenação de grandes conjuntos de dados.

Pior Caso

O pior caso para o algoritmo Bubble Sort ocorre quando o arranjo de entrada está ordenado de forma inversa. Nessa situação, o algoritmo tem um custo quadrático de comparações e trocas, em função do número de elementos a serem ordenados:

• O(n²) comparações
• O(n²) trocas

Melhor Caso

O melhor caso para o algoritmo Bubble Sort ocorre quando o arranjo de entrada já está ordenado. Nessa situação, o algoritmo tem um custo linear de comparações e um custo constante de trocas, em função do número de elementos a serem ordenados:

• O(n) comparações
• O(1) trocas

Como implementar o Bubble Sort?

Veja o código completo no GitHub.