TOP 25 ALGORITMOS | Quick Sort

É um algoritmo de classificação baseado em Dividir e Conquistar que escolhe um elemento como pivô e particiona o array fornecido em torno do pivô escolhido, colocando o pivô em sua posição correta no array classificado.

📁 | Resumo

🤖 | Código

function partition(arr, low, high){


  // Escolha o pivô
  let pivot = arr[high];


  // Índice do menor elemento e indica a posição correta do pivô encontrada até agora
  let i = low - 1;


  // Percorre arr[low..high] e move todos os elementos menores para o lado esquerdo. Elementos de low para i são menores após cada iteração
  for (let j = low; j <= high - 1; j++) {
      if (arr[j] < pivot) {
          i++;
          swap(arr, i, j);
      }
  }


  // Move o pivô após elementos menores e retorna sua posição
  swap(arr, i + 1, high);
  return i + 1;
}


function swap(arr, i, j){
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

🕰️ | Complexidade de Tempo

✦ Melhor Cenário: ocorre quando o elemento pivô divide a matriz em duas metades iguais O(Ω ∙ (n ∙ log (n)));

✦ Cenário Comum: em média, o pivô divide a matriz em duas partes, mas não necessariamente iguais O(θ ∙ (n ∙ log (n)));

✦ Pior Cenário: ocorre quando o menor ou maior elemento é sempre escolhido como pivô (por exemplo, matrizes classificadas), O(n²);

📦 | Complexidade de Espaço

Requer apenas um espaço de memória extra temporária. Logo, sua complexidade de espaço será descrita por O(n).

✔️ | Vantagens

✦ Rápido;

✦ Baixa sobrecarga de memória;

✦ Eficiente em grandes conjuntos de dados;

❌ | Desvantagens

✦ Não é estável;