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;
}Links úteis
- Como Usar std::function em C++
- Como usar e pra que serve a biblioteca magic_enum
- Conceitos sobre new e delete em C++
- Funções Variádicas em C++
algoritmos cpp cppdaily programacao desenvolvimento
