Quicksort

QuickSort
Algoritmos e Estuturas de Dados
Inverno 2006

Cátia Vaz

1

QuickSort
Algoritmo do tipo dividir para conquistar Ideia do algoritmo: efectuar partição dos dados e ordenar as várias partes independentemente (de forma recursiva) posicionamento da partição a efectuar depende dos dados de entrada processo de partição é crítico uma vez efectuada a partição, cada uma das partes pode por sua vez ser ordenada pelo mesmo algoritmo .
Cátia Vaz
2

QuickSort-partição public static void quicksort(int a[], int left, int right){ int i; if (right = j) break; exch(a[i], a[j]);

} exch(a[i], a[right]); return i; }

Cátia Vaz

6

QuickSort-partição
Processo de partição não é estável qualquer chave pode ser movida para trás de várias outras chaves iguais a si (que ainda não foram examinadas)

A eficiência do processo de ordenação depende de como a partição divide os dados (do elemento de partição) será tanto mais equilibrada quanto mais perto este elemento estiver do meio do array na sua posição final

Cátia Vaz

7

QuickSort-características
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 / 2 (mesma situação se o ficheiro estiver ordenado por ordem inversa) Nota: Não apenas o tempo necessário para a execução do algoritmo cresce quadraticamente como o espaço necessário para o processo recursivo é de cerca de N o que é inaceitável para ficheiros grandes.

Cátia Vaz

8

QuickSort-características
Melhor caso: quando cada partição divide o ficheiro de entrada exactamente em metade número de comparações usadas por quicksort satisfaz a recursão de dividir para conquistar C(N)= 2 C( N /2) + N

e logo

C(N) =O( N log N)

Cátia Vaz

9

QuickSort-características