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!
Top comments (1)
Ótimo artigo, o algoritmo quicksort é o mais utilizado porém nunca tinha visto a sua implementação utilizando o clojure