Quicksort

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (716 palavras )
  • Download(s) : 0
  • Publicado : 23 de novembro de 2011
Ler documento completo
Amostra do texto
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 asvá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 podepor 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 aindanã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 elementoestiver 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 nopior 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 processorecursivo é 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 emmetade
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...
tracking img