Quicksort
Quicksort usa a técnica de dividir e conquistar de uma maneira diferente. Procede da seguinte forma:
- Escolha um elemento arbitrário da matriz (o pivô).
- Divida a matriz em dois segmentos, os elementos menores que o pivô e os elementos maiores, com o pivô no meio (a fase de partição).
- Classifique recursivamente os segmentos à esquerda e à direita do pivô.
No quicksort, dividir o problema em subproblemas será o tempo linear, mas juntar os resultados é imediato. Esse tipo de troca é frequente no projeto de algoritmos. Analisando a complexidade assintótica da fase de particionamento de o algoritmo. Tendo o array:
3, 1, 4, 4, 7, 2, 8
e escolhendo 3 como pivô. Então tem que comparar cada elemento deste (não classificado) array para o pivô para obter uma partição onde 2, 1 estão à esquerda e 4, 7, 8, 4 estão à direita do pivô. Escolhe-se uma ordem arbitrária para os elementos nos segmentos da matriz: tudo o que importa é que todos os menores os maiores estão à esquerda do pivô e todos os maiores estão à direita. Como tem que comparar cada elemento com o pivô, mas caso contrário apenas colete os elementos, parece que a fase de partição do algoritmo deve ter complexidade O(k), onde k é o comprimento do segmento da matriz que tem que particionar.
Deve ficar claro que no caso ideal (melhor), o elemento pivô será magicamente o valor mediano entre os valores da matriz. Isso significa apenas que metade dos valores terminará na partição esquerda e metade dos valores terminará na partição certa. Então se parte do problema de ordenar um array de comprimento n para uma matriz de comprimento n/2.
Em cada nível, o trabalho total é de O(n) operações para executar a partição. No melhor caso haverá O(log n) níveis, levando-nos ao O(n log n) complexidade assintótica de melhor caso. Quantas chamadas recursivas temos no pior caso e quanto tempo são os segmentos da matriz? No pior caso, sempre escolhemos o menor ou o maior elemento da matriz para que um lado da partição seja vazio e o outro tem todos os elementos, exceto o próprio pivô.
Todas as outras chamadas recursivas estão com o segmento vazio do array, já que nunca ter quaisquer elementos não classificados menores que o pivô. Ver isso na pior caso haja n − 1 chamadas recursivas significativas para um array de tamanho n. O k-ésima chamada recursiva tem que classificar um subarray de tamanho n − k, que prossegue por particionamento, exigindo O(n − k) comparações. [1]
function quickSort(array) {
if (array.length <= 1) {
return array;
}
const pivot = array[0];
const left = [];
const right = [];
for (let i = 1; i < array.length; i++) {
if (array[i] < pivot) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
const array = [3, 1, 4, 4, 7, 2, 8];
const ordenado = quickSort(array);
console.log(ordenado); // Saida: [1, 2, 3, 4, 4, 7, 8]