Algoritmos de Ordenação - Introdução

O que é um Algoritmo?

Um algoritmo é, essencialmente, um procedimento computacional que, por meio de uma sequência de passos bem definidos, converte uma determinada entrada em uma saída específica. Em termos gerais, podemos considerá-lo como uma ferramenta para solucionar problemas.

Faço um paralelo com a Matemática, minha área de origem. Podemos comparar a construção de um teorema a um processo de resolução de problemas. No famoso teorema de Pitágoras, temos uma entrada: um triângulo retângulo qualquer. Buscamos chegar a uma saída: a prova de que a soma dos quadrados dos catetos é igual ao quadrado da hipotenusa. Para alcançar isso, seguimos uma sequência de passos lógicos, utilizando alguma estratégia. Temos as provas diretas e provas por redução ao absurdo, ao supormos o contrário. Algoritmos funcionam de maneira semelhante! Temos um caso inicial e queremos chegar a algo desejado; para isso, há uma sequência de passos a seguir. Além disso, existem abordagens distintas, como a incremental e a divisão e conquista, que são técnicas renomadas para a criação de algoritmos.

O problema da Ordenação

A ordenação é uma ideia simples de conceber e, mesmo que você nunca tenha escrito um único "Hello World" em toda a sua vida, com certeza, no cotidiano, já nos deparamos com situações em que precisamos ordenar ou somos ordenados: lista de tarefas, senhas em filas de bancos ou clínicas médicas, lista de contatos do celular, entre outros. Poderíamos passar o dia inteiro dando exemplos de problemas que envolvem ordenação.

Mas por que ordenar? Essa resposta depende do domínio do problema. No entanto, se temos um conjunto de elementos desordenados, realizar uma busca neles se torna uma tarefa bem mais complicada. Imagine uma biblioteca sem sessões divididas em categorias, sem ordem alfabética; com certeza, você demoraria muito mais tempo procurando a obra de seu interesse. É nesse sentido que a ordenação nos ajuda.

Existem inúmeros algoritmos de ordenação, e aqui vou criar uma lista de posts para cada um deles.

Critérios utilizados para análise

Em sua renomada obra "The Art of Computer Programming", Donald Knuth nos guia pelos fundamentos da Análise de Algoritmos. Para aqueles familiarizados com o básico do Cálculo diferencial e integral, o termo "assintótica" pode soar conhecido, pois Knuth popularizou essa abordagem para avaliar o uso de recursos computacionais, como tempo de execução e memória.

No estudo do Cálculo, dedicamos muito tempo a analisar o comportamento das funções. Nos limites, torna-se comum trabalhar com os conceitos de assíntotas horizontais e verticais. São linhas que se aproximam infinitamente de uma curva, mas nunca a tocam ou a cruzam. Sempre as imaginei como limitadores, marcando claramente onde a função se estabiliza.

Você pode se perguntar: "O que o Cálculo tem a ver com escrever código em Python?" Aí reside a beleza da análise de algoritmos. Um código consiste em linhas de texto que representam operações a serem realizadas. Cada operação tem um custo variável, que é o tempo que a sua máquina leva para executar aquela linha. O código executa essa mesma linha vezes, dependendo do caso. Se somarmos os produtos do custo de cada operação e a quantidade de vezes que é executada para uma entrada genérica, podemos montar uma função T(n) que representa o tempo de execução em função do tamanho da entrada.

Assim, no final, chegamos a uma função de natureza desconhecida, dependendo do código em questão. No entanto, mesmo para códigos pequenos, podemos nos deparar com problemas, como resolver várias recorrências e somatórios, resultando em uma expressão gigantesca igualmente difícil de imaginar manualmente como deve ser aquele gráfico.

Foi aqui que surgiu a genial sacada: "Ok, esta função gigantesca eu não sei como é, mas se fosse x², eu saberia." A ideia é simplesmente a seguinte: uma função terá um termo predominante. No caso de funções polinomiais, o termo predominante é o de maior grau. Ignoramos a constante que pode estar associada a esse termo e todas as outras. Assim, uma expressão cheia de constantes e termos é resumida a, por exemplo, log⁡x ou x, facilitando muito a comparação dos gráficos.

"Mas não perdemos qualidade na análise fazendo uma aproximação bruta da função?" Sim, perdemos. No entanto, aí entra o conceito de análise assintótica. Para analisarmos se um algoritmo é melhor que outro, aplicamos nossa entrada a valores absurdamente altos. E, quando os valores de entrada são tão elevados, a diferença se torna irrelevante, permitindo-nos descartar sem medo o resto da função e usar o termo predominante.

Compreender esses conceitos é de importância ímpar! Se não compreender esses conceitos básicos, não conseguirá fazer suas próprias análises e muito menos entender o motivo por trás de uma tomada de decisão algorítmica.