Definição – o que significa Bubble Sort?
A classificação por bolha é um algoritmo de classificação que funciona percorrendo repetidamente as listas que precisam ser classificadas, comparando cada par de itens adjacentes e trocando-os se estiverem na ordem errada. Este procedimento de aprovação é repetido até que nenhuma troca seja necessária, indicando que a lista está classificada. A classificação por bolha recebe esse nome porque elementos menores borbulham em direção ao topo da lista.
A classificação por bolha também é conhecida como classificação por afundamento ou classificação por comparação.
Definirtec explica Bubble Sort
A classificação por bolha tem um pior caso e uma complexidade média de O (n2), onde n é o número de itens classificados. Ao contrário dos outros algoritmos de classificação, a classificação por bolha detecta se a lista classificada é construída de forma eficiente no algoritmo. O desempenho da classificação por bolha em uma lista já classificada é O (n).
A posição dos elementos no tipo de bolha 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 início. Como tal, esses elementos são chamados de coelhos e tartarugas.
O algoritmo de classificação por bolha 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, pulando assim o rastreamento das variáveis trocadas.