No mundo dos algoritmos, o QuickSort é um dos mais eficientes e amplamente utilizados. Ele se destaca pela sua habilidade de ordenar grandes volumes de dados de forma rápida e eficiente, graças à sua estratégia de Dividir para Conquistar (DC). Vamos explorar como o QuickSort funciona!

O que é QuickSort?

QuickSort é um algoritmo de ordenação que utiliza a estratégia de Dividir para Conquistar. Ele escolhe um elemento chamado pivô e divide a lista em dois subarrays: um com elementos menores que o pivô e outro com elementos maiores. A recursão é aplicada aos subarrays, até que a lista esteja completamente ordenada.

A escolha do pivô pode ser feita de várias maneiras. Por exemplo, uma abordagem simples é escolher o primeiro elemento da lista. No entanto, essa não é uma regra, e outras escolhas também podem ser feitas, dependendo do caso.

Etapas do QuickSort

1. Base da Recursão

Quando a lista tem 0 ou 1 elemento, ela já está ordenada, e o algoritmo não precisa fazer mais nada.
java


// Verifique se a lista tem 0 ou 1 elemento, que já está ordenada
if (integerList.isEmpty() || integerList.size() < 2) {
    return integerList;
}

2. Divisão da Lista:

O próximo passo é escolher um pivô e dividir a lista em dois subarrays: um com elementos menores e outro com elementos maiores que o pivô. O código abaixo mostra como isso pode ser feito:

var pivo = integerList.getFirst();
for (int i = 1; i < integerList.size(); i++) {
   if (integerList.get(i) <= pivo) {
      menores.add(integerList.get(i));
   }
   if (integerList.get(i) > pivo) {
      maiores.add(integerList.get(i));
   }
}
Importante: Observe que a comparação começa a partir de i=1, para evitar que o pivô seja colocado no subarray de menores.

3. Recursividade:

Agora, a recursividade entra em ação! O algoritmo chama a função quickSort novamente para os subarrays de menores e maiores, repetindo o processo até que a lista esteja ordenada. Aqui está o código para combinar os resultados:


var sorted = new ArrayList<>(quickSort(menores));
sorted.add(pivo);
sorted.addAll(quickSort(maiores));
return sorted;

A Complexidade do Algoritmo

O QuickSort tem uma notação Big O de O(n log n), o que significa que ele é muito eficiente, especialmente quando comparado a algoritmos como o Bubble Sort, que tem O(n²).
Nota: Esta explicação é uma adaptação do Capítulo 4 do livro Entendendo Algoritmos, de Aditya Bhargava. Reforço que pode haver falhas, então é sempre bom revisar o conteúdo!

Conclusão

O QuickSort é um algoritmo poderoso que utiliza recursão para ordenar listas de forma eficiente. Sua principal vantagem é o tempo de execução, que pode ser muito rápido em listas grandes, especialmente quando comparado a outros algoritmos de ordenação. Se você deseja entender mais profundamente a fundo, recomendo a leitura do livro Entendendo Algoritmos.

Já utilizou o QuickSort em algum projeto real? Compartilhe nos comentários!

Author Of article : Lucas Oliveira Read full article