Ordenação rápida - Quick Sort

Ú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.

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

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

Entendo algoritmos - Aditya Y. Bhargava

Wikpédia quick sort