sexta-feira, 24 de abril de 2015

Programação em C - Quicksort

Olá pessoal, em posts anteriores falamos sobre diversos algoritmos de ordenação tais como Insertion Sort, Selection Sort, Bubble Sort, Heap Sort e Merge Sort. Nesse post iremos falar sobre o Quicksort (ordenação rápida).

O Quicksort é um método bastante utilizado, assim como o Mergesort, ele utiliza a estratégia de divisão e conquista (quebra um problema em subproblemas menores). O caso médio do Quicksort é O(nlogn) e O(n^2) no pior caso.

Você pode está achando que não é uma boa usar o Quicksort porque o HeapSort e MergeSort têm complexidade nlogn no pior caso, mas esse post irá esclarecer o porquê que o Quicksort é a melhor escolha na maioria das vezes.

O pior caso do Quicksort pode ser quase sempre evitado usando uma versão randômica para nos dar nlogn no pior caso. A nossa implementação contemplará isso.

Quicksort é in place (ao contrário do Mergesort). Um método in place é aquele que o espaço extra necessário não cresce de acordo com a quantidade de elementos.

A complexidade de espaço mede a taxa de crescimento do espaço extra necessário. Espaço extra significa espaço ou memória além da memória usada para armazenar o vetor original.

No caso médio o Quicksort possui complexidade de espaço O(logn) e no pior caso possui O(n), mas nós já dissemos que o pior caso pode ser evitado não é mesmo? Então vamos considerar O(logn), logn é muito pequeno, por isso o Quicksort é in place, pois utiliza memória extra constante, ou seja, o espaço extra necessário não deve crescer com a entrada. Como logn para todos os valores de "n" é muito pequeno, então desconsideramos aqui e dizemos que o Quicksort é in place. Um exemplo de método que não é in place é o MergeSort.

O Quicksort não é estável, ou seja, não mantém a ordem dos registros com chaves iguais. O MergeSort por exemplo é estável, já o HeapSort e SelectionSort não são estáveis.

A partição é o ponto chave do Quicksort, ela consome theta(n). Uma partição balanceada nos dará o melhor caso, ou seja, teremos o melhor caso quando as 2 sublistas tiverem tamanhos iguais (à esquerda e à direita do pivô).

Como já foi dito, o pior caso do Quicksort pode ser evitado. Na implementação, fizemos uma função chamada "particiona_random" que seleciona um pivô aleatoriamente e troca de posição com o último elemento, pois nessa implementação sempre escolhemos o último elemento como pivô. Fazendo aleatório conseguimos evitar quase sempre o pior caso do Quicksort.

Outra forma de escolher o pivô é selecionar três itens aleatórios e pegar a mediana dos três como pivô (não fizemos isso na nossa implementação).

Outra melhoria que pode ser feita é interromper as partições para vetores pequenos utilizando um dos algoritmos básicos para ordená-los tais como inserção ou seleção (não fizemos isso na nossa implementação).

Basicamente o quicksort escolhe o pivô, particiona o conjunto em dois subconjuntos, ordena cada conjunto separadamente e concatena o elemento pivô e os 2 subconjuntos ordenados em um único subconjunto.

Para entender melhor como funciona, assista a essas duas excelentes vídeo-aulas, a implementação foi baseada nelas:




Veja a implementação utilizando a linguagem C:



Nenhum comentário: