DEV Community

Lucas Oliveira
Lucas Oliveira

Posted on

Entendendo o Algoritmo QuickSort: Dividir para Conquistar

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.

Image description

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

Image description

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

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));
   }
}
Enter fullscreen mode Exit fullscreen mode

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:

Image description

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

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!

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay