Quando você iria querer o bubblesort? • Botão para baixo

Existem muito poucas regras universais em engenharia de software, mas existem muitas aproximar-princípios universais. Coisas como “preferir composição à herança” são quase universais. Adoro encontrar as raras situações em que esses princípios não são válidos, como quando você deseja herança em vez de composição. Um princípio quase universal semelhante é “não use bubblesort”. Alguns diriam até que é uma regra universal, com Donald Knuth escrevendo “o tipo bolha parece não ter nada que o recomende, exceto um nome atraente e o fato de que leva a alguns problemas teóricos interessantes”. ^{Mas Knuth já esteve errado antes, então vamos ver se esta regra universal é apenas aproximar-universal.}

Teoricamente, o bubblesort é mais rápido que o quick ou mergesort para arrays pequenos. Isso o torna útil como parte de uma estratégia de classificação maior: a maioria dos algoritmos de classificação rápidos em princípio funcionam classificando recursivamente subpartições de uma matriz, ou seja, se você aplicar quicksort a 2 ^ 20 números inteiros aleatórios, em algum momento você estará classificando 2 ^ 17 subpartições de 8 inteiros. Mudar para o bubblesort para essas subpartições seria uma boa otimização.

Muitos algoritmos de classificação de produção usam uma abordagem híbrida, mas, em vez disso, usam predominantemente a classificação por inserção. A classificação por inserção é muito rápida para arrays pequenos e também é melhor no uso do hardware. Em alguns hardwares muito específicos, o bubblesort ainda é melhor, como neste estudo da NVIDIA, mas você provavelmente não tem esse hardware.

Portanto, esse é um caso de uso, embora ainda dominado por um algoritmo diferente. É interessante que a NVIDIA tenha usado isso aqui porque o gamedev tem uma situação que é exclusivamente útil para o bubblesort, com base em duas de suas propriedades:

1. Embora o algoritmo seja muito lento em geral, cada etapa individual é muito rápida e facilmente suspendível.
2. Cada troca deixa o array mais ordenado do que antes. Outras classificações podem mover valores ausente de suas posições finais em estágios intermediários.

Isso é muito bom quando você deseja fazer uma quantidade fixa de trabalho de classificação por quadro. Digamos que você tenha vários objetos em uma tela, onde alguns objetos podem obstruir outros. Você deseja renderizar os objetos mais próximos da câmera primeiro porque então você pode determinar quais objetos ele oculta e economizar tempo ao renderizar esses objetos. Não há custo de correção para renderizar objetos fora de ordem, apenas um custo potencial de desempenho. Então, embora seu array não precisar para ser encomendado, quanto mais ordenado, mais feliz você fica. Mas você também não pode gastar muito tempo executando um algoritmo de classificação, porque você tem uma restrição de tempo real bastante estrita. A classificação por bolha funciona muito bem aqui. Você pode executá-lo um pouco em cada quadro e obter uma ordem melhor do que quando começou.

Isso me lembra um último caso de uso que ouvi, apócrifamente. Digamos que você tenha uma coleção aleatória de partículas de cores aleatórias e queira animá-las classificando-as em um espectro de arco-íris. Se você fizer uma passagem de bubblesort para cada quadro da animação, todas as partículas se moverão suavemente para as posições corretas. Não consegui encontrar nenhum exemplo, então, com a ajuda do GPT4, criei uma visualização de baixa qualidade. O código está aqui, coloque-o aqui.

(Depois de fazer isso, suspeito que isso não seja feito na prática, em favor de executar uma classificação melhor para calcular o deslocamento final de cada partícula e, em seguida, animar cada partícula se movendo diretamente, em vez de esperar para se mover para cada passagem do bubblesort. Não zombei de um exemplo, mas acho que ficaria muito mais suave.)

Então aí está, três casos de uso de nicho para bubblesort. Você provavelmente nunca precisará disso.

Novo Artigo Quanta!

Ok, na verdade não escrevi este, mas desempenhei um papel nisso! Há algum tempo, um amigo nos visitou e estávamos conversando sobre seu trabalho na quanta. Na época, ele estava trabalhando neste artigo gigantesco sobre a teoria da metacomplexidade, então, naturalmente, surgiu o tópico de problemas mais difíceis do que NP-completo e recomendo que ele dê uma olhada na acessibilidade da rede de Petri. Foi o que ele fez, e então escreveu Um problema que parece fácil produz números grandes demais para o nosso universo. Puxa, isso é tão emocionante!