Dança dos algoritmos

Ae, povo,

O pessoal da Universidade Sapientia, na Transilvânia, resolveu fazer coreografias dos principais algoritmos para ordenação utilizando-se de danças folclóricas locais. O grupo, denominado AlgoRythmics, fez coreografias dos algoritmos de ordenação por seleção, por inserção, pela bolha, shell sort (não conhecia) e os dois principais algoritmos recursivos para ordenação, o quick-sort e o merge-sort.

Para quem não sabe, o problema da ordenação é o de pegar uma sequência qualquer de números e ordená-los de forma crescente. Este é um problema bastante estudado na computação por ser um problema relativamente simples, mas que pode introduzir vários conceitos importantes, como, de acordo com a Wikipedia, limites superior e inferior, a notação O, recursão, divisão e conquista, estruturas de dados, algoritmos aleatórios, melhor, pior, ou caso médio de execuções, entre outras coisas.

O algoritmo de ordenação por seleção é bem simples. Selecione o menor de todos e coloque-o na frente. Dos restantes, selecione o menor, e coloque-o na frente. Este, vai ser o 2º menor da sequencia toda, e vai ficar na 2ª posição. Dos restantes, selecione o menor e coloque-o na frente. Este, vai ser o 3º menor de todos, e vai ficar na 3ª posição. E assim, vai, até o final.

O algoritmo de ordenação por inserção também é bem simples. Pegue o 1º número da sequência. Ele, por si só, já está ordenado. Pegue o 2º número da sequência, e coloque-o antes ou depois do 1º, dependendo se este for menor ou maior. Os dois primeiros números já estão ordenados. Pegue o 3º número, e coloque-o antes, entre, ou depois dos 2 primeiros. Estes 3 números estão ordenados entre si. E por aí vai, sempre pegando o próximo número e colocando-o de forma apropriada, respeitando a ordenação de parte dos elementos.

O quick-sort é um algoritmo recursivo bem legal. Algoritmos recursivos são aqueles que se usam para resolver problemas menores durante a resolução de problemas maiores. No caso do quick-sort, acontece da seguinte forma. Escolha um número qualquer da sequência. Divida a sequência, colocando os menores que esse número à esquerda e os maiores, à direita. Agora, ordene essas duas subsequências. E como ordenar essas duas subsequências? Ora, para cada uma, escolha um número qualquer, divida essa subsequência em duas (sub)subsequências, colocando os menores de um lado e os maiores do outro lado, e ordene cada uma dessas (sub)subsequências. Ou seja, aplique o mesmo algoritmo do quick-sort, só que para sequências menores. E faça isso até que tenha-se somente um elemento na sequência, caso em que este elemento, por si só já está ordenado.

Bom, é isso. Confiram os outros algoritmos, se quiserem. Valeu. Correspondente Anônimo.