Entendendo Algoritmos - Cap.5 Quicksort em Clojure
Tags: clojure, quicksort, algorithms, lisp
Published: 2023-10-16 02:08:36

> Este mês estou participando do clube de leitura #devslendo [(Mais informações aqui)](https://twitter.com/loremimpsu/status/1707020185515773989) em que o livro escolhido é o [Entendendo Algoritmos](https://www.amazon.com.br/Entendendo-Algoritmos-ilustrado-programadores-curiosos-ebook/dp/B07B61HC3L). 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](https://www.youtube.com/watch?v=wx5juM9bbFo) 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](https://www.youtube.com/watch?v=wx5juM9bbFo) 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](https://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](https://carlacastanho.github.io/Material-de-APC/aulas/aula14.html)

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/as1h5ca3a2bns64w0nda.png)

## 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!