O algoritmo Quicksort

O algoritmo Quicksort, nos testes executados apresenta o maior número de comparações e o menor número de trocas. É um algoritmo eficiente apesar do seu pior caso ser O(n2). O Mergesort possui um pior caso O(n log n), no entanto utiliza memória auxiliar e possui um alto consumo de memória. Já o Inserção Binária apresenta um pior caso O(n2), e mesmo apresentando um melhor caso O(n log n) ainda sim é um algoritmo de inserção. Dessa forma é possível inferir que o algoritmo Quicksort é possivelmente o mais indicado para diversas situações.

O Comportamento do Quicksort é demonstrado nas seguintes imagens.

(a) Melhor caso, quando os dados de entrada são aleatórios ou parcialmente ordenados e o pivô é o registro do meio.

(b) Caso Médio.

(c) Pior Caso, ocorre quando o vetor esta ordenado (asc. ou desc.). Dessa forma o algoritmo irá particionar o arranjo com n elementos em 2 arranjos sendo 1 com n-1 elementos e outro com apenas 1 elemento, diminuindo o problema em apenas 1 elemento.

O Quick Sort no melhor caso sempre escolhe o elemento mediano da sua lista de entrada como pivô. O pior caso do Quicksort justamente na pior escolha do pivô: um elemento extremo da lista (no inicio ou no final). Testes com entradas aleatórias e pivôs escolhidos aleatoriamente mostram que a complexidade do Quicksort, mesmo nestes casos, se aproxima muito do tempo de O(n log n).

* melhor caso: O(n log n)

* pior caso: O(n2)

* caso médio: O(n log n)

* Não é estável