Quicksort

Páginas: 3 (716 palavras) Publicado: 23 de novembro de 2011
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...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • QuickSort
  • QuickSort 2
  • QuickSort ( Algoritmo )
  • Método de Ordenação Quicksort
  • QuickSort MIPS
  • Metodos de ordenação
  • Trabalho De Estrutura De Dados Quicksort
  • Implementação do quicksort co o uso de threads em java

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!