Pages Menu
TwitterRssFacebook
Categories Menu

Algoritmos de ordenação: colocar as coisas em ordem nem sempre é fácil

por em 14/12/2018 em Ciência, Notícias | Nenhum comentário

Algoritmos de ordenação: colocar as coisas em ordem nem sempre é fácil

Eu sempre acho um pouco estranho quando as pessoas falam que “os computadores são mais inteligentes que os humanos” — na verdade, nós que somos inteligentes o suficiente pra fazer máquinas que possam resolver problemas muito complexos. Na verdade, esse é o verdadeiro problema.

Um computador é uma máquina capaz de realizar um zintilhão de operações matemáticas por segundo (sendo um zintilhão uma ordem de grandeza cada vez maior conforme os anos passam). Mas, pelo menos por enquanto, quem decide quais contas ele deve fazer, em qual momento deve fazer somos nós. Basicamente, isso é o que programadores fazem, isso é o que chamamos de algoritmo: uma sequência de passos que devem ser executados para fazer alguma coisa.

Esse texto não é sobre algoritmos no geral. Na verdade, é sobre um problema bem simples (muito simples mesmo), que você consegue realizar de forma fácil — mas que, quando você para pra pensar, não é tão fácil fazer o computador fazê-lo.

Basicamente, eu te dou um saco com 100 cartas numeradas. Eu preciso que você coloque-as em ordem crescente.

Como você resolveria?

A verdade é que nós temos muitas formas diferentes de fazer isso. Cada um tem a sua, inclusive. Você poderia fazer um monte com as cartas e começar a ir colocando na ordem dentro da sua mão ou ficar com todas elas já na mão e ficar trocando ali mesmo.

Dependendo do número de cartas, você também faria de um jeito diferente. Se fossem 5 ao invés de 100, era só colocar elas em cima da mesa e ir pegando elas de volta na ordem. Tudo bem, você poderia fazer isso com 100 também, só demoraria um pouco mais.

Fonte da imagem: GIPHY

Fonte da imagem: GIPHY

O problema é que um computador não pode ordenar uma série de números como você fez, cada hora de um jeito, até que tudo esteja pronto. Ele precisa de uma estratégia bem definida pra isso, que possa funcionar pra qualquer quantidade de números.

E na falta de um jeito só… existem vários. Ordenar números é uma das tarefas mais básicas e mais importantes da computação (vários outros algoritmos só conseguem funcionar, ou executam de forma mais eficiente, se o conjunto de dados estiver previamente ordenado) e, há tempos, vários cientistas da área estão procurando diversas maneiras de fazê-lo.

Simples (e lento): a ordenação por seleção

Um dos algoritmos mais simples é conhecido como selection sort (ou “ordenação por seleção”) pois toda a ideia dele é focado em você procurar, um de cada vez, o menor dos elementos que você precisa ordenar. Vamos novamente para as nossas cartas para entender melhor como funciona.

Imagine que você colocou todas as cartas em qualquer ordem em cima de uma mesa (bem grande, por sinal, pra caber 100 delas). O nosso algoritmo consiste em você, a cada vez que olhar para a sequência, sempre ter a menor carta possível na mão. Pegue a primeira carta e compare-a com todas as outras, sempre na sequência: mantenha a menor na sua mão e devolva a outra para o lugar que estava vazio.

Fonte da imagem: Code Pumpkin

Fonte da imagem: Code Pumpkin

Quando você fizer isso com todas as cartas, você vai acabar com a menor das cartas, independente de quais números tiver nela. Sendo assim, você sabe que ela deve ficar no começo da sequência.

Agora, é só repetir o processo ignorando a primeira carta – assim, você vai ter a segunda menor carta na mão depois que olhar a sequência inteira. Coloque-a logo depois da primeira e repita de novo, ignorando as duas. Depois de algum tempo, você terá todas as cartas em ordem!

E como você deve ter pensado, isso é, sim, bem lento. O selection sort sempre faz (n² – n) / 2 comparações, sendo n o número de elementos que você deseja ordenar. Para as nossas 100 cartas, seriam 4950 comparações. Se você demorar 1 segundo para cada uma, você levaria quase 1 hora e meia para deixar tudo na ordem! Mesmo que um computador faça isso muito mais rápido, ele tem que lidar com trilhões de coisas ao invés de apenas centenas, então, no fim das contas, não vale a pena usar essa técnica, por mais que ela seja um jeito bem metódico de conseguir ordenar coisas.

Caso você tenha algum baralho ou qualquer outra coisa que possa ordenar aí do seu lado, tente fazer! Se não tiver, você pode acompanhar essa… dança?

A clássica ordenação de bolha

Vamos tentar uma outra abordagem que, por mais que também não seja também tão eficiente, é um verdadeiro clássico em qualquer aula de programação básica: a ordenação de bolha (ou bubble sort). Ele baseia-se também em comparar dados em pares, como fazíamos antes, mas agora, sempre fazemos com números que estão adjacentes.

Lembra das nossas 100 cartas? Precisamos voltar pra elas, coloque-as de novo em cima de uma grande mesa, em qualquer ordem. Agora, pegue as duas primeiras na mão: se a carta da esquerda for maior que a da direita, troque-as de lugar; caso não, pode deixar como está. Assim, sempre a menor carta estará à esquerda e a maior, à direita.

Fonte da imagem: Code Pumpkin

Fonte da imagem: Code Pumpkin

Repita o processo, agora com a segunda e a terceira carta, sempre deixando a maior carta no espaço da direita. Faça isso até a penúltima e a última carta. Ao fim do processo, a maior carta de todas estará na última posição, com 100% de certeza. Mesmo que ela, originalmente, fosse a primeira carta da sequência, como ela é a maior de todas, ela sempre seria jogada à direita, exatamente na posição para fazer a próxima comparação e novamente ser jogada pra frente, até o último espaço.

Agora que você sabe que a última carta já está no lugar certo, é só repetir o processo ignorando-a. Dessa forma, a segunda maior carta ocupará o penúltimo espaço, a terceira maior o antepenúltimo, e por aí vai, até que tudo esteja devidamente ordenado. Algumas versões dele, inclusive, nem fazem isso até o final e param se você passar por todas as cartas que sobrarem e não trocar nenhuma delas de lugar (nesse caso, você já pode garantir que todas estão no lugar certo).

É… O bubble sort não só parece lerdo, ele É realmente lerdo. No pior caso, onde absolutamente todas as trocas devem ser feitas – inclusive, isso acontece quando ele está ordenado, mas no sentido errado; no nosso caso, de forma decrescente -, ele realiza n² trocas de cartas. Para as nossas 100, seriam 10000 trocas! Agora imagine para 4 trilhões de números… Faz sentido procurarem uma alternativa melhor, né?

Sim, tem dancinha de novo! (nota do redator: elas são muito engraçadas)

Uma tarefa difícil, mas não impossível!

Ordenar números, como podemos ver, está longe de ser algo trivial para um computador. Nós só vimos duas, mas várias outras maneiras existem para fazer isso – todas elas com seus prós e contras e que ficarão para futuras oportunidades.

Da próxima vez que você pensar em um computador como uma máquina sensacional, que tudo vê e tudo faz, nunca deixe de lembrar de todas as pessoas que estão por trás dela: engenheiros, cientistas, programadores. Afinal, foram eles que ficaram horas e horas para saber como criar um algoritmo para uma coisa que parecia tão idiota, né…

Modo Noturno