image

Acesse bootcamps ilimitados e +650 cursos

50
%OFF
Article image
Isadora Ariane
Isadora Ariane18/11/2024 13:00
Compartilhe

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

    image

    🤖 | 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;

    Compartilhe
    Comentários (0)