Quicksort

Quicksort usa a técnica de dividir e conquistar de uma maneira diferente. Procede da seguinte forma:

1. Escolha um elemento arbitrário da matriz (o pivô).
2. 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).
3. 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.

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]