Introdução
Existem vários meios para ordenar uma base, meios esses que na programação dão o surgimeto para vários tipos de algoritmos como , bubble sor , merge sort , quick sort entre outros. Esses métodos possuem várias abordagens diferentes e seu uso pode variar para desde casos muito específicos de ordenação como também para casos genéricos e simples mas hoje vamos lhe apresentar um em especifico que será o quck sort.
Mais afinal o que é o quick sort ?
O quick sort como já tenho dito, é um algoritmo ordenação criado para ordenar grandes bases de dados no menor tempo e com o menor nível de complexidade computacional possível, claro que ele pode sofrer variações a depender de casos muito especifico esse algoritmo em comparação com outros algoritmos de ordenação de dados que temos conhecimento tende a ser o mais performático, além de que o quick sort pode ser implementados de forma eficiente no local, o que economiza espaço de memória.
Mas embora tudo como ele surgiu afinal ?
Por volta dos anos de 1960, C.A.R. Hoare , um estudante assim como todos vocês, frequentava a Universidade de Moscovo na Russia onde fazia parte de um projeto de tradução de máquina onde
ele tentava fazer com que a máquina pudesse traduzir um dicionário em inglês para o russo, contudo devido problemas com a organização das palavras ele decidiu tentar organizar-las , tendo como objetivo reduzir o problema original em subproblemas o que possibilitava que os problemas fossem resolvidos mais rápido.
Dois anos depois em 1960, Hoare apresenta para o mundo a sua solução para ordenar esses dados com um pouco mais de refinamento e qualidade resultando no surgimento do quick sort. Então peso que prestem bastante atenção porque a partir de agora nós mostraremos pra vocês as nuncias , as falhas os acertos e suas curiosidades desse interessante algoritmo de ordenação chamado quick sort.
Tudo bem até aqui, mais como ele funciona?
O quick sort se baseia na estratégia de dividir para conquistar, onde a cada execução do algoritmo ele divide a nossa base de dados em duas partes até que ele chegue na menor parte irredutível que seria 01. Após ele chegar na menor parte da nossa base de dados ele volta subindo e criando comparações para ordenar cada pedaço dividido até chegar no topo novamente com as duas partes ordenadas.
como funciona a comparação de ordenação?
Basicamente, temos um pivô que será um número escolhido aleatoriamente em cada sub divisão da base de dados esse é o nosso pivô, que será usado para dividir os nossos dados em elementos menores que o pivô e elementos maiores que eles é ir comparando um a um e ordenando cada elemento em sua ordem correta até chegar ao topo novamente. Nesse método conseguimos garantir que a cada comparação seja sempre bastante rápida devido sempre repartimos os nossos dados em partes pequena então sempre executamos comparações simples e rápidas ao invés de comparações longas e extensas nos poupando tempo.
exemplo das comparações :
Curiosidade…
Um ponto interessante nesse seguimento e que a medida que os anos foram passando as pessoas foram desenvolvendo estudos para melhorar a eficiência de tais algoritmos incluindo o próprios quick sort que em 2009 o Yaroslavskiy desenvolveu o Dual-Pivot Quicksort que se baseava na implementação de um segundo pivô a mais no algoritmo padrão. Yaroslavskiy demonstrou que o uso de dois pivôs é mais eficaz, especialmente quando possui uma quantidade maior de dados de entrada, comprovando a sua vantagem em relação ao algoritmo quicksort clássico.
Baseado nesse estudo do Yaroslavskiy foi desenvolvido um experimento realizado pelo Budiman, Zamzami e Rachmawati (2017), foi proposto, implementado e realizado experimentos com os algoritmos quicksort clássico e quicksort com dois, três, quatro e cinco pivôs. Analisando os resultados experimentais notou-se que o quicksort com um único pivô é o mais lento entre as cinco. Em segundo lugar, analisando o uso de até 5 pivôs foi comprovado que quanto mais pivôs são utilizados em um algoritmo quicksort, mais rápido seu desempenho se torna. Em terceiro lugar, o aumento de velocidade resultante da adição de mais pivôs tende a diminuir gradualmente.
Entendemos o que seria o algoritmo, mais porque usa-lo?
Seguindo esse pensamento podemos ser influenciados para usa-lo devido a sua alta eficiência em ordenar altos níveis de dados com uma complexidade media de O(N log N), que é bastante boa considerando outros algoritmos conhecidos. Outro fator que pode influenciar o seu uso é o fator de que ele é in-place, o que significa que ele ordena os elementos sem a necessidade de espaço extra significativo. Isso o torna ideal para sistemas com recursos limitados. Além disso, o Quick Sort é altamente paralelizável, o que permite que ele seja executado em múltiplos núcleos de processamento, aumentando ainda mais sua velocidade em ambientes modernos de computação.
Então isso significa que ele é perfeito para todos os casos ?
Embora o Quick Sort seja um dos algoritmos de ordenação mais eficientes, ele não é perfeito para todos os casos.
Ele apresenta dificuldades ao lidar com conjuntos de dados quase ordenados, o que pode aumentar significativamente sua complexidade de tempo. Além disso, a escolha inadequada do pivô pode levar a repartições muito desequilibradas, resultando no pior caso do algoritmo, que tem complexidade O(N²). Apesar de existirem técnicas para mitigar esse problema, como a escolha aleatória do pivô ou o método da mediana de três, ainda é um fator a ser considerado.
Outro ponto importante é que o Quick Sort não é um algoritmo estável, ou seja, ele não mantém a ordem relativa de elementos iguais. Isso pode ser um problema em aplicações onde essa estabilidade é essencial.
Por esses motivos, apesar de ser uma das melhores opções para ordenação na maioria dos casos, o Quick Sort pode não ser a escolha ideal em situações específicas.
Comparação com outros algoritmos de ordenação
O quicksort é um algoritmo eficiente de ordenação baseado no conceito de dividir e conquistar. Ele pode ser comparado a uma árvore binária ordenada, mas, em vez de construir uma árvore explícita, organiza os elementos implicitamente por meio de chamadas recursivas. No final, ele realiza as mesmas comparações que uma árvore binária de busca, mas de forma mais otimizada.
Quicksort vs. Heapsort
O algoritmo mais parecido com o quicksort é o heapsort. Ambos têm um desempenho médio semelhante, mas o pior caso do heapsort tem complexidade O(n log n), enquanto o quicksort pode ter desempenho O(n²) se a escolha do pivô for ruim.
Por outro lado, o quicksort tende a ser mais rápido na prática devido ao seu acesso eficiente à memória. O introsort é uma variante do quicksort que detecta um pior caso e automaticamente muda para o heapsort, garantindo que a complexidade não ultrapasse O(n log n). Se já se sabe de antemão que o pior caso ocorrerá, pode ser melhor usar o heapsort diretamente para evitar a troca de algoritmo durante a execução.
Quicksort vs. Mergesort
O mergesort também é um algoritmo recursivo, como o quicksort, mas sua grande vantagem é que ele tem complexidade garantida de O(n log n) no pior caso. Além disso, o mergesort é estável, o que significa que ele mantém a ordem relativa de elementos iguais, o que pode ser importante para algumas aplicações.
Outra vantagem do mergesort é que ele funciona muito bem em listas encadeadas e em grandes volumes de dados armazenados em disco ou em redes. O quicksort, por outro lado, pode ter dificuldades nesses casos, especialmente se não houver acesso aleatório eficiente aos elementos.
A principal desvantagem do mergesort é que ele exige O(n) de espaço adicional, o que pode ser um problema quando se trabalha com grandes conjuntos de dados. Já o quicksort usa apenas O(log n) de espaço devido à sua abordagem recursiva e particionamento in-place, tornando-o mais eficiente em termos de uso de memória.
Quicksort vs. Bucket Sort
O bucket sort com dois baldes (buckets) se assemelha ao quicksort, pois também divide os elementos em grupos menores antes de ordená-los. A diferença principal é que, no bucket sort, o pivô sempre será o valor central do vetor, o que pode evitar os piores casos do quicksort em algumas situações.
implementação em python :
#include <iostream>
#include <fstream>
#include <vector>
#include <chrono>
#include <thread>
#include <algorithm>
using namespace std;
int medianaDeTres(int vetor[], int menor, int maior) {
int meio = menor + (maior - menor) / 2;
if (vetor[menor] > vetor[meio])
swap(vetor[menor], vetor[meio]);
if (vetor[menor] > vetor[maior])
swap(vetor[menor], vetor[maior]);
if (vetor[meio] > vetor[maior])
swap(vetor[meio], vetor[maior]);
return meio;
}
int particao(int vetor[], int menor, int maior) {
int pivoIndex = medianaDeTres(vetor, menor, maior);
swap(vetor[pivoIndex], vetor[maior]);
int pivo = vetor[maior];
int i = menor - 1;
for (int j = menor; j < maior; j++) {
if (vetor[j] < pivo) {
i++;
swap(vetor[i], vetor[j]);
}
}
swap(vetor[i + 1], vetor[maior]);
return i + 1;
}
void quickSort(int vetor[], int menor, int maior) {
while (menor < maior) {
int pi = particao(vetor, menor, maior);
if (pi - menor < maior - pi) {
quickSort(vetor, menor, pi - 1);
menor = pi + 1;
} else {
quickSort(vetor, pi + 1, maior);
maior = pi - 1;
}
}
}
void quickSortParalelo(int vetor[], int menor, int maior, int profundidade = 0) {
if (menor < maior) {
int pi = particao(vetor, menor, maior);
if (profundidade < 4) {
thread esquerda(quickSortParalelo, vetor, menor, pi - 1, profundidade + 1);
quickSortParalelo(vetor, pi + 1, maior, profundidade + 1);
esquerda.join();
} else {
quickSort(vetor, menor, pi - 1);
quickSort(vetor, pi + 1, maior);
}
}
}
bool Importar_txt(const string &endereco, vector<int> &numeros) {
ifstream arquivo(endereco);
if (!arquivo) {
cerr << "Erro ao abrir o arquivo " << endereco << endl;
return false;
}
int num;
while (arquivo >> num) {
numeros.push_back(num);
}
arquivo.close();
return true;
}
bool salvar_txt(const string &endereco, const vector<int> &numeros) {
ofstream arquivo(endereco);
if (!arquivo) {
cerr << "Erro ao abrir o arquivo para escrita: " << endereco << endl;
return false;
}
for (size_t i = 0; i < numeros.size(); i++) {
arquivo << numeros[i] << (i < numeros.size() - 1 ? "\n" : "");
}
arquivo.close();
return true;
}
int main() {
string endereco = "../50_milhoes.txt";
vector<int> numeros;
auto codigo_tempo = chrono::high_resolution_clock::now();
if (!Importar_txt(endereco, numeros)) {
return 1;
}
int tamanho = numeros.size();
int *vetor = numeros.data();
auto inicio = chrono::high_resolution_clock::now();
quickSortParalelo(vetor, 0, tamanho - 1);
auto resultado = chrono::high_resolution_clock::now() - codigo_tempo;
long long milissegundos = chrono::duration_cast<chrono::milliseconds>(resultado).count();
double segundos = chrono::duration<double>(resultado).count();
if (!salvar_txt(endereco, numeros)) {
return 1;
}
auto codigo_tempo_resultado = chrono::high_resolution_clock::now() - inicio;
long long tempo_milissegundos = chrono::duration_cast<chrono::milliseconds>(codigo_tempo_resultado).count();
double tempo_segundos = chrono::duration<double>(codigo_tempo_resultado).count();
cout << "\nArquivo atualizado com os números ordenados." << endl;
cout << "\nTempo do Algoritmo por completo:" << endl;
cout << " Tempo em milissegundos: " << tempo_milissegundos << endl;
cout << " Tempo em segundos: " << tempo_segundos << endl;
cout << "\nTempo do QuickSort:" << endl;
cout << " Tempo em milissegundos: " << milissegundos << endl;
cout << " Tempo em segundos: " << segundos << endl;
return 0;
}
Onde o Quicksort é Usado?
O quicksort é um dos algoritmos de ordenação mais eficientes e, por isso, é amplamente utilizado em diversas áreas da computação. Vamos ver alguns exemplos onde ele aparece no dia a dia:
1. Banco de Dados
Os bancos de dados precisam organizar grandes quantidades de informações para que as buscas sejam rápidas. O quicksort ajuda na ordenação de registros, facilitando a busca de nomes, números e outros dados de forma eficiente.
2. Sistemas Operacionais
Os sistemas operacionais precisam gerenciar diversas tarefas ao mesmo tempo. O quicksort pode ser usado para organizar processos na fila de execução, ajudando o computador a decidir qual tarefa rodar primeiro.
3. Funções de Ordenação em Linguagens de Programação
Muitas linguagens de programação usam o quicksort (ou variações dele) para ordenar listas e arrays de forma rápida. Por exemplo:
- O Python usa o Timsort, que combina quicksort e mergesort.
- O C++ e o Java costumam usar Introsort, que começa com quicksort e troca para heapsort em casos ruins.
4. Jogos e Gráficos Computacionais
Nos jogos e programas que trabalham com gráficos, o quicksort pode ser usado para organizar objetos na tela, como decidir quais devem aparecer na frente ou atrás (exemplo: renderização de sombras e efeitos visuais).
5. Inteligência Artificial e Aprendizado de Máquina
Algoritmos de inteligência artificial precisam organizar grandes volumes de dados para análises. O quicksort ajuda a estruturar essas informações de maneira eficiente.
Conclusão
O quicksort é, sem dúvida, um dos algoritmos de ordenação mais eficientes e amplamente utilizados na computação. Sua estratégia de dividir para conquistar permite um desempenho rápido na maioria dos casos, tornando-o uma excelente escolha para lidar com grandes volumes de dados. Além disso, sua implementação in-place economiza espaço, e sua eficiência prática o coloca como uma das principais opções em linguagens de programação, bancos de dados e sistemas operacionais.
No entanto, como qualquer algoritmo, ele tem suas limitações. O quicksort pode apresentar um desempenho ruim em dados quase ordenados ou quando a escolha do pivô não é ideal, levando à complexidade O(N²) no pior caso. Além disso, sua instabilidade pode ser um problema em aplicações que exigem a manutenção da ordem original dos elementos iguais.
Por isso, ao escolher um algoritmo de ordenação, é fundamental entender o contexto e as necessidades específicas da aplicação. O quicksort brilha em cenários de uso geral devido à sua velocidade e eficiência, mas alternativas como mergesort e heapsort podem ser mais adequadas em casos onde estabilidade ou pior caso previsível são preocupações.
Referencias :
https://medium.com/@amndalsr/quicksort-entendendo-o-algoritmo-b31b0807fd95
https://medium.com/enjoy-algorithm/quicksort-one-the-fastest-sorting-algorithms-2685fb0910c5
Top comments (0)