O algoritmo de ordenação Maggie
É um dos problemas clássicos em computação. Como ordenar uma lista de elementos? O prazer (ou desculpa) de organizar discos em ordem alfabética agora é substituído por um clique que faz a tarefa em frações de segundo. Mas fazê-lo nas menores frações de segundo possíveis, encontrando o algoritmo de ordenação mais eficiente, é o que torna este problema aparentemente trivial um tema de pesquisa até hoje.
Ou, como Eric Schmidt do Google perguntou a Barack Obama, “qual é a maneira mais eficiente de ordenar um milhão de inteiros de 32 bits?”.
Incrivelmente, o presidente responde “acho que bubble sort não seria o caminho certo”. Incrível porque, se a piada não foi combinada, a resposta é uma saída muito boa. O algoritmo bubble sort, de simples implementação e entendimento intuitivo rápido, é no entanto um dos mais ineficientes. Não é recomendado para listas maiores que uma dezena, muito menos de 1 milhão de elementos. Combinado ou não, a piada em si prova que temos o primeiro presidente nerd da era moderna.
Mesmo o algoritmo de ordenação Maggie pode acabar sendo mais eficiente que o bubble sort. A garotinha de 4 anos testa duas caixas por vez, mas é capaz de vasculhar todas as caixas bem como de criar pilhas diferentes de caixas ordenadas. Além de ser muito mais bonitinha. Resta ver se o Ricbit calcula a complexidade desse algoritmo. [via Kenjiria]
Não há conhecimento isolado: qualquer informação só é relevante no contexto de outras. E nada melhor para explorar esta teia de infinitos nexos do que um blog na rede.
Em 100nexos, este autor, 
Discussão - 5 comentários
Observando o maggie sort, a gente vê que ela usa características intrínsecas dos objetos a serem ordenados para decidir a posição dos mesmos: Ela consegue ver pelo "encaixe" de um cubinho no outro se ele é o correto para aquela posição ou não. Também ela parte do conhecimento prévio de qual é o menor (ela vai direto no menor, sem precisar fazer nenhuma comparação). Eu diria que é uma variação do [url]http://en.wikipedia.org/wiki/Pigeonhole_sort[/url], com uma pitada de não determinismo. Uma heurística baseada no Pigeonhole sort. O pior caso continua sendo O(n^2), mas o caso médio e o melhor caso são O(n).
Eu descreveria o algoritmo assim:
def sort(A):
A resposta do Obama é realmente incrível, deve ter sido combinada, não? Quer dizer, é o tipo de tecnicalidade que não é exatamente difícil, mas obscura para gente não envolvida com ciência da computação ou programação e mesmo quem é pode acabar esquecendo o nome desse tipo de ordenação.
E a garotinha ordenando é realmente uma graça... Excelente artigo.
hahaha obrigado, girino! A intuição estava certa, é um pouco melhor que bubble sort! 😀
Eu fiz uns testes aqui e basicamente depende da estratégia de escolha do próximo bloco. Se a escolha for relativamente inteligente (i.e. eu sempre sei qual o próximo bloco, com um erro pequeno) o algorítmo é O(e . N) ~= O(N), onde e é o erro médio, inclusive no pior caso. Já se a escolha for burra e eu tenho de tentar aleatoriamente todos os blocos até achar o correto, então e ~= N e o algoritmo passa a ser O(N^2), inclusive no caso médio. O melhor caso é sempre O(N).
[...] em 100nexos, já apresentamos o fabuloso algoritmo de ordenação Maggie. [via haha.nu] Tags computadores, humor, [...]