DEV Community 👩‍💻👨‍💻

Daniel Dormin
Daniel Dormin

Posted on

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.

Image description
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))

Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)

All DEV content is created by the community!

Hey, if you're landing here for the first time, you should know that this website is a global community of folks who blog about their experiences to help folks like you out.

Sign up now if you're curious. It's free!