CP Teoria Ordenacao Parte2 2 C pia

CLASSIFICAÇÃO E PESQUISA

MÉTODOS DE ORDENAÇÃO
PARTE II
PLT PAG. 95

Prof. Juliana Santiago Teixeira [e-mail] QUICKSORT
 Proposto por Hoare em 1960 e publiccado em
1962
 É o algoritmo de ordenação interna mais rápido que se conhece para uma ampla variedade de situações  Provavelmente é o mais utilizado

QUICKSORT
 A idéia básica é dividir o problema de ordenar um conjunto com n itens em dois problemas menores  Os problemas menores são ordenados independentemente  Os resultados são combinados para produzir a solução final

QUICKSORT
 A parte mais delicada do método é o processo de partição
 O vetor A[Esq..Dir] é rearranjado por meio da escolha arbitrária de um pivô x
 O vetor A é particionado em duas partes:
 A parte esquerda com chaves menores ou iguais a x
 A parte direita com chaves maiores ou iguais a x

QUICKSORT
 Algoritmo para o particionamento:
1. Escolha arbitrariamente um pivô x
2. Percorra o vetor a partir da esquerda até que
A[i] ≥ x

3. Percorra o vetor a partir da direita até que
A[j] ≤ x
4. Troque A[i] com A[j]

5. Continue este processo até os apontadores i e j se cruzarem QUICKSORT
 Ao final, o vetor A[Esq..Dir] está particionado de tal forma que:


Os itens em A[Esq]; A[Esq + 1]; ... ; A[j] são menores ou iguais a x



Os itens em A[i]; A[i + 1]; ... ; A[Dir] são maiores ou iguais a x

QUICKSORT

QUICKSORT
 O pivô x é escolhido como sendo
A[(i + j)/2]
 Como inicialmente i = 1 e j = 6, então x = A[3] = D
 Ao final do processo de partição i e j se cruzam em i = 3 e j = 2

void particao(ITEM a[], int esq, int dir, int *i, int *j)
{
ITEM x, w;
*i = esq; *j = dir; x = a[(*i+*j)/2]; do { while (x.chave > a[*i].chave) (*i)++; while (x.chave < a[*j].chave) (*j)--; if (*i<=*j){

w = a[*i]; a[*i] = a[*j]; a[*j] =w;
(*i)++; (*j)--;
}
} while (*i<=*j);

}

// particao

void ordena(ITEM a[], int esq, int dir)
{
int i, j; particao(a, esq, dir, &i, &j); if (esq < j)

ordena(a, esq, j); if (i < dir)
ordena(a,