Classificação por bolha

PerformanceEdit

A classificação por bolha tem pior caso e complexidade média de О (n2), onde n é o número de itens sendo classificados. A maioria dos algoritmos de classificação práticos tem um pior caso substancialmente melhor ou complexidade média, geralmente O (n log n). Mesmo outros algoritmos de classificação О (n2), como classificação por inserção, geralmente são executados mais rapidamente do que classificação por bolha e não são mais complexos. Portanto, a classificação por bolha não é um algoritmo de classificação prático.

A única vantagem significativa que a classificação por bolha tem sobre a maioria dos outros algoritmos, até mesmo a classificação rápida, mas não a classificação por inserção, é a capacidade de detectar se a lista está classificada com eficiência é integrado ao algoritmo. Quando a lista já está classificada (melhor caso), a complexidade da classificação por bolha é apenas O (n). Em contraste, a maioria dos outros algoritmos, mesmo aqueles com melhor complexidade de caso médio, executam todo o seu processo de classificação no conjunto e, portanto, são mais complexos. No entanto, a classificação por inserção não apenas compartilha essa vantagem, mas também tem um desempenho melhor em uma lista substancialmente classificada (com um pequeno número de inversões). Além disso, se esse comportamento for desejado, ele pode ser trivialmente adicionado a qualquer outro algoritmo verificando a lista antes da execução do algoritmo.

A classificação por bolha deve ser evitada no caso de grandes coleções. Não será eficiente no caso de uma coleção ordenada inversamente.

Rabbits and TurtlesEdit

A distância e direção que os elementos devem se mover durante a classificação determinam o desempenho da classificação por bolha porque elementos se movem em direções diferentes em velocidades diferentes. Um elemento que deve se mover em direção ao final da lista pode se mover rapidamente porque pode participar de trocas sucessivas. Por exemplo, o maior elemento da lista vencerá todas as trocas, então ele se move para sua posição classificada na primeira passagem, mesmo se começar perto do início. Por outro lado, um elemento que deve se mover em direção ao início da lista não pode se mover mais rápido do que uma etapa por passagem, então os elementos se movem em direção ao início muito lentamente. Se o menor elemento está no final da lista, serão necessárias n-1 passagens para movê-lo para o início. Isso fez com que esses tipos de elementos fossem chamados de coelhos e tartarugas, respectivamente, após os personagens da fábula de Esopo de A tartaruga e a lebre.

Vários esforços têm sido feitos para eliminar as tartarugas para melhorar a velocidade do tipo bolha. O tipo coquetel é um tipo de bolha bidirecional que vai do começo ao fim e depois se inverte, indo do fim ao começo. Ele pode mover tartarugas razoavelmente bem, mas retém a complexidade de pior caso O (n2). A classificação de pente compara elementos separados por grandes lacunas e pode mover tartarugas extremamente rapidamente antes de prosseguir para lacunas cada vez menores para suavizar a lista. Sua velocidade média é comparável a algoritmos mais rápidos, como quicksort.

Exemplo passo a passo Editar

Pegue uma matriz de números “5 1 4 2 8” e classifique a matriz a partir do menor número para o maior número usando a classificação por bolha. Em cada etapa, elementos escritos em negrito estão sendo comparados. Três passagens serão necessárias;

Primeira passagem (5 1 4 2 8) → (1 5 4 2 8), aqui, o algoritmo compara os dois primeiros elementos e troca desde 5 > 1. (1 5 4 2 8) → (1 4 5 2 8), Trocar desde 5 > 4 (1 4 5 2 8) → (1 4 2 5 8), Troca desde 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), Agora, uma vez que esses elementos já estão em ordem (8 > 5), o algoritmo não os troca. Segunda passagem (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), Trocar desde 4 > 2 ( 1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)

Agora, a matriz já está classificada, mas o algoritmo não sabe se está concluída . O algoritmo precisa de uma passagem inteira sem nenhuma troca para saber que está classificado.