Ordenação rápida - Quick Sort
Tags: braziliandevs, algorithms, javascript, algoritmos
Published: 2022-11-11 15:43:52

Último post dessa série de algoritmos de ordenção! Já falamos do Bubble sort e do Selection sort, hoje vamos falar de um algoritmo que pode ser usado em seus projetos! O Quick sort, um algoritmo rápido que sua notação big O em O(n log n) no caso médio o que é bem melhor do que tinhamos antes nos algoritmos anteriores.

##Como ele funciona?
O quicksort adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar de modo que os números maiores fiquem a direita do pivô e os números menores a esquerda, fazendo isso de forma recursiva, assim a lista fica cada vez menor.

Os passos são:

- Escolha um elemento da lista, denominado pivô;
- Particiona: rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, 
e todos os elementos posteriores ao pivô sejam maiores que ele.Ao fim do processo o pivô estará em sua posição final e 
haverá duas sub listas não ordenadas.Essa operação é denominada partição;
- Recursivamente ordene a sub lista dos elementos menores e a sub lista dos elementos maiores;
- O caso base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas.O processo é finito, 
pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.

A escolha do pivô e os passos do Particiona podem ser feitos de diferentes formas e a escolha de uma implementação específica afeta fortemente a performance do algoritmo.
A Imagem a baixo exemplifica bem como é feita divisão.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r8xco3mmscn7dow2k5yp.png)
A escolha do pivô pode ser feita de forma aleátória ou por uma regra.

O código é bem consiso e simples por não usar loop é totalmente aplicavel em códigos funcionais com algumas alterações dentro da função :D
```JavaScript

let arr = [17, 14, 23, 2, 4, 9, 15, 1, 0, 3, 5]
function quicksort(array) {
    if (array.length <= 1) {
        return array
    }

    let pivot = array[0]

    let left = []
    let right = []

    for (let i = 1; i < array.length; i++) {
        array[i] < pivot ? left.push(array[i]) : right.push(array[i])
    }

    return quicksort(left).concat(pivot, quicksort(right))
}

console.log(quicksort(arr))

```
No código como dito criamos uma função, definimos um pivô e criamos dois arrays auxiliares um para a direita e um para esquerda, é feito um loop para comparar os valores e colocarem no array certo, seja ele para esquerda ou para direita, depois concatatenamos e chamamos a função novamente até que o array esteja totalmente dividido para retornar o array ordenado, como visto na condicional de parada na linha 3.

Muito obrigado por ler até aqui, fiquem a vontade em me enviar dúvidas comentários ou críticas.


##Referências

<a target="_blank" href="https://www.amazon.com.br/Entendendo-Algoritmos-Ilustrado-Programadores-Curiosos/dp/8575225634/ref=sr_1_1?keywords=entendo+algoritmos&amp;qid=1665248064&amp;qu=eyJxc2MiOiIwLjczIiwicXNhIjoiMC4yOSIsInFzcCI6IjAuMzQifQ%253D%253D&amp;sprefix=entendo+al%252Caps%252C234&amp;sr=8-1&_encoding=UTF8&tag=dormin0f-20&linkCode=ur2&linkId=c4974c19ccad271886d077fca1397935&camp=1789&creative=9325">Entendo algoritmos</a> - Aditya Y. Bhargava 

[Wikpédia quick sort](https://pt.wikipedia.org/wiki/Quicksort)