Algoritmos de Ordenação - QuickSort

O que é?

É um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960. Naquela época, Hoare ainda era estudante e trabalhou em um projeto de tradução de máquina para o National Physical Laboratory. Ele criou o quicksort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais fácil e rápido. Após alguns refinamentos, o método foi publicado em 1962.

O quicksort adota a estratégia de divisão e conquista. A mesma

consiste em rearranjar os valores de modo que as "menores" fiquem atrás das "maiores". Em seguida o quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada. Os passos são:

1. Escolher um elemento da lista, denominado pivô;
2. Rearranjar a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sub listas não ordenadas. Essa operação é denominada partição;
3. Ordenar recursivamente a sub lista dos elementos menores e a sub lista dos elementos maiores;

O caso base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo não é infinito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.

A escolha do pivô e os passos de partição podem ser feitos de diferentes formas e a escolha de uma implementação específica afeta fortemente a performance do algoritmo.

Aqui um vídeo em inglês que explica o conceito em dois minutos:
https://www.youtube.com/watch?v=HDQd6_0TJIE
Uma implementação em C:
http://www.programasprontos.com/algoritmos-de-ordenacao/algortimo-quick-sort/
Uma explicação teórica do Departamento de Matemática da USP:
https://www.ime.usp.br/~pf/algoritmos/aulas/quick.html
Explicação rápida do conceito:
https://pt.wikipedia.org/wiki/Quicksort

Share: