Ú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
Top comments (0)