Entendendo Algoritmos - Cap.5 Quicksort em Clojure

Este mês estou participando do clube de leitura #devslendo (Mais informações aqui) em que o livro escolhido é o Entendendo Algoritmos. No capítulo 5, é apresentado o Quicksort. Assim como no outro artigo, não irei explicar o conceito, pois o livro já o faz muito bem. A ideia aqui não é ser mais um resumo, mas sim mostrar como implementar na prática usando Clojure.

Quicksort

O quicksort é um algoritmo de ordenação. Este algoritmo é muito mais rápido do que a ordenação por seleção e é muito utilizado na prática. por exemplo, a biblioteca-padrão da linguagem C tem uma função chamada qsort, que é uma implementação do quicksort. O algoritmo quicksort também utiliza a estratégia DC (Dividir e Conquistar).
Aditya Y. Bhargava

Além do livro, sugiro também esse vídeo para quem gostaria de entender mais sobre o quicksort.

Implementando Quicksort com clojure

Vou dar uma breve introdução sobre o que é o quicksort. Basicamente, temos um vetor, e para ordená-lo, escolheremos um pivô. O pivô servirá de base para nossa comparação. Após a primeira iteração com esse vetor, teremos todos os valores menores que o pivô ao lado esquerdo e todos os maiores ou iguais ao lado direito. Para isso, dado o seguinte vetor:

[3 4 5 2 1 6 7 3]

Vamos escolher o primeiro elemento como nosso pivô. Seguindo a regra acima, teríamos o seguinte resultado:

esquerda [2 1]
pivô 3
direita [4 5 6 7 3]

"E repetiremos a execução para cada subgrupo, selecionando um novo pivô nesse subgrupo (esquerda e direita). Sei que essa explicação é bem breve e sucinta, por isso recomendo esse vídeo para que você entenda bem o conceito.

Quicksort no Clojure

O Clojure é uma linguagem funcional que tem como um de seus princípios a imutabilidade, isso significa que um valor não sofre alterações ao longo da execução. Isso garante a confiabilidade nos dados e evita side-effects inesperados. Temos que levar isso em conta ao implementar o algoritmo de Quicksort.
Iremos utilizar a recursividade, para trabalhar os subgrupos, até que todo o vetor esteja devidamente ordenado. Irei explicar cada passo da função.

A Função

(ns entendendo-algoritmos-clojure.recursion.quicksort)

(defn execute
  [values]
  (let [pivot (last values)
        remaining-values (butlast values)
        left (filter #(< % pivot) remaining-values)
        right (filter #(>= % pivot) remaining-values)]
    (flatten (concat (if (> (count left) 1) (execute left) left)
                     [pivot]
                     (if (> (count right) 1) (execute right) right)))))

Caso queira testar a função acima, basta acessar o replit.com, criar um novo repl do tipo Clojure, colar a função acima e, logo na linha debaixo, adicionar uma chamada como por exemplo:

(execute [4 5 2 3 7 8 1])

O resultado deverá ser o vetor ordenado [1 2 3 4 5 7 8]

O nome da função é execute, pois o namespace já contem o contexto de quicksort: (ns entendendo-algoritmos-clojure.recursion.quicksort)

Entendendo a função

A primeira coisa sobre nossa função é que recebemos o parâmetro values, que irá representar nosso vetor na função. Logo em seguida, temos a seção (let []) onde definimos alguns símbolos para organizar nosso código. O let funciona da seguinte forma, dentro de colchetes temos nossos símbolos, seguindo a seguinte lógica:"

(let [simbolo valor
      simbolo-2 valor-2])

Onde simbolo passa a representar o valor que está logo a sua direita, por exemplo:

(let [filme "O auto da compadecia"])

Para utilizar os símbolos, precisamos estar dentro do escopo do let, portanto, antes de fechar seu parênteses. Entenda por símbolo o que, em outras linguagens, chamamos de propriedade, variável ou constante, o que nesse caso faz mais sentido, uma vez que seu valor nunca muda. Nesse caso, se quisermos imprimir o valor, faríamos da seguinte forma:

(let [filme "O alto da compadecia"]
(print filme))
; Imprime no console: O auto da compadecia

Note que antes de fechar o parênteses do let, chamamos a instrução (println simbolo). Isso acontece porque os símbolos criados no let só existem dentro do seu escopo.

Ok, agora que você entende um pouco mais sobre o escopo e como o let funciona para criar nossos símbolos locais. Vamos entender o que cada símbolo representa.
Começando pelo nosso pivot. Iremos utilizar a função last que retorna o último item do nosso array. Ele seria o equivalente a values[values.length - 1], como é visto na maioria das linguagens.

Em seguida, para não repetirmos o próprio item na lista, iremos criar uma nova lista, descartando o pivot, para isso, utilizaremos a função butlast.

Para o símbolo left, filtramos a lista com os valores menores que o pivot, e em right os valores maiores ou iguais ao pivot, utilizando a função filter, que possui dois parâmetros: o predicado e uma lista. O predicado é simplesmente uma condição para filtrar nossa lista, trazendo apenas os itens desejados. No caso de left, queremos todos os itens menores que o pivot, então usamos (< % pivot), onde % representa cada um dos elementos de values:

(filter #(< % pivot) remaining-values)

OBS: No Clojure, sempre começamos a comparação com o operador, então em vez de % < pivot, escrevemos < % pivot.

Caso base

Se não sabe o que é um caso base na recursividade sugiro a leitura desse link

O nosso caso base acontece quando o vetor (left ou right) possui apenas um elemento, nesse caso ao invés de chamarmos a função recursivamente, iremos apenas retornar o próprio vetor.
(if (> (count right) 1) (execute right) right)
Se você não está acostumado com a sintaxe Clojure, saiba que o if também é uma função e, nesse caso, ela espera três parâmetros:
(if predicate value-when-true value-when-false)

Então, para a nossa função, se o número de itens for maior que um, ela irá chamar novamente a função execute para aquele subvetor, caso contrário, retornará o próprio subvetor. Note que fizemos o mesmo para left e right, então seguem o mesmo princípio.

Nesse momento vamos então concatenar left + [pivot] + right. Então, uma certeza que temos é que nossa função sempre terá um pivô no meio da concatenação, e consequentemente, tudo que está à esquerda é menor que ele e tudo à direita é maior.

Simplificando o concat sem o if teriamos a seguinte concatenação:

(concat left [pivot] right)

Substituindo os símbolos por valores:

(concat [3 2 1] [4] [5 6 8 7])

Isso tem como resultado:
[3 2 1 4 5 6 8 7]

E por fim, como a recursão poderá retornar listas dentro de listas, temos o flaten que faz o achatamento dos dados.
Por exemplo:

(flaten [2 [2 3 [4]] [5 6] 8])

Retorna o dado achatado:
[2 2 3 4 5 6 8]

Como a função se resolve

Na imagem a seguir, ilustrei o que acontece em cada iteração da função execute e como os blocos da concatenação são organizados naquele momento. Portanto, sempre teremos três blocos na seguinte sequência: left, pivot e right.
O item que será o nosso pivô naquela interação está destacado em vermelho.

Ficamos por aqui

Espero que o exemplo tenha te ajudado a visualizar o quicksort na prática dentro do paradigma funcional.

Agradeço a todos que chegaram até aqui e peço, por favor, que me ajudem com seu feedback. Comentem se os exemplos foram claros ou se sentiram falta de algum ponto que não abordei. Ficarei feliz em ajudá-los!