Quicksort.

Se queremos ordenar um monte de peças numeradas podemos pegar numa de cada vez e ir alinhando. Pomos a primeira no chão, a segunda encostada à esquerda ou a direita, se for preciso chegamos uma para o lado para pôr a terceira e assim por diante até ter todas numa fila ordenada. Isto é um algoritmo, uma sequência de instruções simples que dá um resultado pretendido.

Uma propriedade importante de qualquer algoritmo é a sua complexidade. Não no sentido de ter instruções difíceis de seguir ou de nos perdermos a meio, mas o número esperado de operações que cada problema obriga a executar. Neste caso, temos de tirar as peça do monte uma de cada vez, tantas vezes quantas forem as peças. Chamemos n ao número de peças. E, para cada peça, temos de olhar para as peças que estão no chão e procurar o sitio certo onde pôr a nova peça. O numero de operações deste procedimento é proporcional ao número de peças que já estão ordenadas. No inicio do processo haverá poucas peças no chão mas, no final, estarão lá quase todas, A média é cerca de metade de n, que também é proporcional a n. Como temos de fazer n vezes um procedimento de complexidade proporcional a n a complexidade do algoritmo todo é C(n²). Ou seja, o trabalho que nos dá ordenar n peças desta maneira é proporcional a n².

Em 1962, Charles Hoare inventou um algoritmo que chamou quicksort. Aplicando-o ao nosso exemplo, primeiro despejamos as peças todas em fila no chão, pela ordem que calhar. Depois escolhemos uma para pivot e pomos à sua direita todas as que tiverem um número maior e à sua esquerda as que tiverem um número menor. Não interessa que cada uma dessas partes fique desordenada, e até podemos fazer isto na mesma fila trocando as peças que estão no lado errado umas com as outras ou com o pivot. Neste passo temos de fazer n operações, acabando com o pivot algures no meio, todas as maiores à direita e todas as menores à esquerda. Agora fazemos o mesmo com cada uma dessas duas partes. Escolhemos um novo pivot e pomos as maiores de um lado e as menores de outro. Depois fazemos o mesmo com cada uma das quatro partes separadas pelos pivots. E com as oito partes seguintes, e assim por diante até ter tudo ordenado.

Em cada um destes passos já não mexemos nos pivots anteriores, porque esses ficaram no sitio certo. Mas o número de operações é à mesma proporcional a n, seja para a fila toda de uma vez, seja quando está partida em duas metades, quatro quartos, etc. A diferença em relação ao algoritmo anterior é que não temos de repetir isto n vezes. Em cada passo estamos a partir os pedaços aproximadamente a meio, e o número de vezes que podemos fazer isso é log₂(n). Se n for cerca de mil, basta partir ao meio dez vezes que temos o trabalho terminado (2¹⁰=1024). A diferença entre C( n² ) e C( n × log₂(n) ) cresce rapidamente com n. Se temos 1000 peças o quicksort é cerca de cem vezes mais rápido. Com 10.000 peças é quase um milhão de vezes mais rápido.

Além de me divertir com estas coisas (é triste, eu sei...), escrevi este post para ilustrar um aspecto importante da intuição. Para quem não lida com este tipo de problemas o quicksort parece um disparate. É uma ideia estranha, pôr umas de um lado, outras do outro e repetir para cada metade. Mas, com a prática, o poder do logaritmo, desta divisão por dois, torna-se intuitivo e uma solução óbvia para diversos problemas como indexar listas, procurar elementos, calcular correlações de matrizes e assim por diante. E esta intuição não se tem antes de compreender o problema. Desenvolve-se com o conhecimento das coisas.

Daí que seja um erro separar a intuição da ciência, como muitos querem fazer para evitar ter de justificar as hipóteses que defendem. As cartas dos tarólogos, o misticismo das medicinas tradicionais, a revelação dos crentes religiosos e tantas outras coisas apresentadas como vias alternativas para o conhecimento não são intuição de confiança. São ilusão e erro, porque a intuição sem conhecimento engana. Diz-nos que o Sol anda pelo céu e que a Terra é plana. Por isso a intuição não é um atalho cómodo para saber sem ter trabalho. É uma das recompensas do esforço metódico e deliberado de compreender as coisas. A intuição deve vir com a ciência, porque sem ciência não é de fiar.

Adenda, 27-6: Nesta página há uns applets em java que demonstram vários algoritmos de ordenação, e podemos pô-los a correr ao mesmo tempo para comparar. Os que menciono no post são o InsertionSort e QSort.