Quicksort

Introducão
Este trabalho é sobre o algoritmo Quicksort, ao longo do trabalho tentamos explicar o funcionamento deste algoritmo, alguns conceitos importantes e como implementar.
O algoritmo Quicksort foi inventado por C.A.R. Hoare, usa o paradigma da divisão e conquista para resolver o problema ele é muito rápido em média, mas lento no pior caso.

Quicksort
O algoritmo Quicksort é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960.
Algoritmo mais popular de ordenação. Na maioria dos casos ele roda em O(NlogN) para ordenações internas ou em memória. Para ordenar informações em arquivos em disco existem métodos melhores.
Particionamento é a base do algoritmo e é chamado de maneira recursiva
É importante ainda a escolha do pivô e como é feito o processo de ordenação. O Quicksort adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "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:
- Escolha um elemento da lista, denominado pivô; - Rearranje 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 sublistas não ordenadas. Essa operação é denominada partição; - Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;

Características do QuickSort

Pode ser muito ineficiente em casos patológicos!
Propriedade: quicksort usa cerca de N2/2 comparações no pior caso.
Demonstração: se o array já estiver ordenado, todas as partições degeneram e o programa chama-se a si próprio N vezes.

o número de comparações é de
N + (N-1) + (N-2) + ... + 2 + 1 = (N + 1) N