Entenda o Algoritmo Quick Sort

⚡️ O Quick Sort é um algoritmo de ordenação eficiente e amplamente utilizado, que segue a abordagem de: dividir para conquistar.


Entenda o Algoritmo Quick Sort


O Quick Sort é um algoritmo de ordenação eficiente e amplamente utilizado, que segue a abordagem de “dividir para conquistar”. Ele funciona da seguinte maneira:

  • 1. Faz escolha de um elemento como pivô do array. Existem várias estratégias para escolher o pivô, como o primeiro elemento, o último elemento, o elemento do meio, ou uma média de três.
  • 2. Depois ele reorganiza o array de tal forma que todos os elementos menores que o pivô ficam à esquerda e todos os elementos maiores que o pivô ficam à direita. O pivô é então colocado em sua posição final.
  • 3. O processo é repetido recursivamente para os subarrays à esquerda e à direita do pivô, até que todos os subarrays estejam ordenados.

Para o algoritmo Quick Sort, a complexidade é O(n²), no pior caso, mas em outras situações, dependendo do pivô escolhido, sua complexidade pode ser: O(n log n) quando o pivô escolhido é consistentemente o menor ou o maior elemento em cada partição.

Vamos ver na prática como implementar o Quick Sort com C++ Moderno!


🎥 Assista ao vídeo


📄 Código desenvolvido no vídeo

#include <iostream>
#include <vector>
#include <functional>

auto partition = [](std::vector<int>& v, int low, int high){
  int pivot = v[high];
  int i = low - 1;
  for (int j = low; j < high; ++j){
    if(v[j] <= pivot){
      ++i;
      std::swap(v[i], v[j]);
    }
  }
  std::swap(v[i + 1], v[high]);
  return i + 1;
};

std::function<void(std::vector<int>&, int, int)> 
quick_sort = [](std::vector<int>& v, int low, int high){
  if(low < high){
    int p = partition(v, low, high);
    quick_sort(v, low, p - 1);
    quick_sort(v, p + 1, high);
  }
};


int main(){
  std::vector<int> v {11, 2, 13, 17, 12, 8, 4};
  quick_sort(v, 0, v.size() - 1);
  for(auto &var : v){
    std::cout << var << ' ';
  }
  std::cout.put('\n');
  return EXIT_SUCCESS;
}


algoritmos cpp cppdaily programacao desenvolvimento


Compartilhe


Nosso canal no Youtube

Inscreva-se


Marcos Oliveira

Marcos Oliveira

Desenvolvedor de software
https://github.com/terroo


Crie Aplicativos Gráficos para Linux e Windows com C++

Aprenda C++ Moderno e crie Games, Programas CLI, GUI e TUI de forma fácil.

Saiba Mais

Receba as novidades no seu e-mail!

Após cadastro e confirmação do e-mail, enviaremos semanalmente resumos e também sempre que houver novidades por aqui para que você mantenha-se atualizado!