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]

Related Posts Plugin for WordPress, Blogger...

Discussão - 5 comentários

  1. Girino disse:

    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):

    # introduz não determinismo, o erro é no máximo de 1
    A2 = [n for n in range(len(A)) + random(-1, 1)]
    for i in range(len(A2)):

    j = i+1
    while A2[i] != i:

    tmp = A2[i]
    A2[i] = A2[j]
    A2[j] = tmp

    return A2

  2. Patola disse:

    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.

  3. Kentaro Mori disse:

    hahaha obrigado, girino! A intuição estava certa, é um pouco melhor que bubble sort! :-D

  4. Girino disse:

    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).

  5. […] em 100nexos, já apresentamos o fabuloso algoritmo de ordenação Maggie. [via haha.nu] Tags computadores, humor, […]

Envie seu comentário

Seu e-mail não será divulgado. (*) Campos obrigatórios.

Arquivos

Páginas

Sobre ScienceBlogs Brasil | Anuncie com ScienceBlogs Brasil | Política de Privacidade | Termos e Condições | Contato


ScienceBlogs por Seed Media Group. Group. ©2006-2011 Seed Media Group LLC. Todos direitos garantidos.


Páginas da Seed Media Group Seed Media Group | ScienceBlogs | SEEDMAGAZINE.COM