Índice:
Definição - O que significa Bubble Sort?
A classificação por bolhas é um algoritmo de classificação que funciona repetidamente percorrendo as listas que precisam ser classificadas, comparando cada par de itens adjacentes e trocando-os se estiverem na ordem errada. Esse procedimento de passagem é repetido até que não sejam necessários swaps, indicando que a lista está classificada. A classificação de bolha recebe esse nome porque elementos menores aparecem na parte superior da lista.
A classificação por bolha também é chamada de classificação por afundamento ou classificação por comparação.
Techopedia explica o Bubble Sort
A classificação de bolha tem uma complexidade média, no pior dos casos, de O (n2), em que n é o número de itens classificados. Diferentemente dos outros algoritmos de classificação, a classificação por bolhas detecta se a lista classificada é incorporada com eficiência no algoritmo. O desempenho da classificação de bolha em uma lista já classificada é O (n).
A posição dos elementos na classificação de bolhas desempenha um papel importante na determinação do desempenho. Elementos grandes no início não representam um problema, pois são facilmente trocados. Os pequenos elementos no final movem-se lentamente para o começo. Como tal, esses elementos são chamados de coelhos e tartarugas.
O algoritmo de classificação de bolhas pode ser otimizado colocando elementos maiores na posição final. Após cada passagem, todos os elementos após a última troca são classificados e não precisam ser verificados novamente, ignorando o rastreamento das variáveis trocadas.
