OrdenaçãoOrdenaçãoQuickSortQuickSort

Prof. César Melo

   

Antes...

● Seja V um vetor com n números inteiros;

● Seja v um número qualquer em V;

● Escreva um algoritmo que divida o vetor V em dois, segundo o seguinte critério:

– Os números menores que v devem ficar na primeira parte do vetor;

– Os números maiores que v devem ficar na segunda parte do vetor

   

Exemplos

16 11 9 8 3 7 2 6 5

2 3 4 5 6 7 8 91

5 2 3 8 9 7 11 6 16

2 3 4 5 6 7 8 91

v = 5

   

Exemplos

5 2 3 8 9 7 11 6 16

2 3 4 5 6 7 8 91

v = 5

3 2 5

2 31

   

Exemplos

5 2 3 6 7 9 11 8 16

2 3 4 5 6 7 8 91

v = 7

5 2 3 8 9 7 11 6 16

2 3 4 5 6 7 8 91

   

Conceitos iniciais

● Algoritmo de ordenação mais rápido que se conhece para uma ampla variedade de situações.

● Usa técnica de Divisão-e-Conquista para ordenar uma sequência com n elementos;

– A sequência é dividida em duas subsequências cada uma com n/2 elementos;

– As duas sequências são ordenadas independentemente;

– O Resultado é então combinado para produzir a solução final.

● Apoia-se em uma função de particionamento.

   

O pequeno código do QuickSort

void quicksort(int p, int r, int A[]){

if (p<r){

q = particao(p, r, A);

quicksort(p, q, A);

quicksort(q+1, r, A);

}

}

   

O particionamento do vetor

● Seja A um vetor com n números;

● Sejam p e r índices de A, com p=1 e r=n;

● Seja x um elemento de A, chamado de pivô, escolhido segundo algum critério;

● Então, usando o valor de x, o vetor A é particionado:

– A parte esquerda com elementos menores ou iguais a x;

– A parte direita com elementos maiores que x.

   

Algoritmo de particionamento

Pseudo-código: Escolha arbitrariamente um pivô x; Percorra o vetor a partir do índice i=p enquanto

A[i]<x; Percorra o vetor a partir do índice j=r enquanto

A[j]>x; Repita este processo até que os índices i e j se

cruzem. Ao final, o vetor [p..r] estará particionado de tal

forma que: Os elementos em A[p...i-1] sejam menores ou

iguais a x; Os elementos em A[i...r] sejam maiores que x;

   

Algoritmo de particionamento

Como é a escolha do pivô? Sorteio;

Usa uma função aleatória;Sempre o elemento no índice central

pivo = A[(p+q)/2]

   

Considere o seguinte vetor A[1..9]

16 11 9 8 3 7 2 6 5

2 3 4 5 6 7 8 91

Aplicando o particionamento quando:•Pivô igual a A[5] = 3;•p=1 e r=9;

   

O pequeno...

void quicksort(int p, int r, int A[]){

if (p<r){

q = particao(p=1, r=9, A);

quicksort(p, q, A);

quicksort(q+1, r, A);

}

}

   

O vetor A[1..9] particionado

2 3 9 8 11 7 16 6 5

2 3 4 5 6 7 8 91

16 11 9 8 3 7 2 6 5

2 3 4 5 6 7 8 91

   

O pequeno...

void quicksort(int p, int r, int A[]){

if (p<r){

q = particao(p=1, r=9, A);

quicksort(p=1, q=2, A);

quicksort(q+1=3, r=9, A);

}

}

Vamos focar AQUI!!

   

O vetor A[3..9] agora...

9 8 11 7 16 6 5

3 4 5 6 7 8 9

   

O pequeno código do QuickSort

void quicksort(int p, int r, int A[]){

if (p<r){

q = particao(p=3, r=9, A);

quicksort(p, q, A);

quicksort(q+1, r, A);

}

}

   

O vetor A[3...9] particionado

5 6 7 11 16 8 9

3 4 5 6 7 8 9

9 8 11 7 16 6 5

3 4 5 6 7 8 9

   

O pequeno...

void quicksort(int p, int r, int A[]){

if (p<r){

q = particao(p=3, r=9, A);

quicksort(p=3, q=5, A);

quicksort(q+1=6, r=9, A);

}

}

Vamos focar AQUI!!

   

O vetor A[6..9] agora

11 16 8 9

6 7 8 9

   

O pequeno código do QuickSort

void quicksort(int p, int r, int A[]){

if (p<r){

q = particao(p=6, r=9, A);

quicksort(p, q, A);

quicksort(q+1, r, A);

}

}

   

O vetor A[6..9] particionado

11 9 8 16

6 7 8 9

11 16 8 9

6 7 8 9

   

O pequeno...

void quicksort(int p, int r, int A[]){

if (p<r){

q = particao(p=6, r=9, A);

quicksort(p=6, q=8, A);

quicksort(q+1=9, r=9, A);

}

}

Vamos focar AQUI!!

   

O vetor A[6..8] agora

8 9 11

6 7 8

   

O pequeno código do QuickSort

void quicksort(int p, int r, int A[]){

if (p<r){

q = particao(p=6, r=8, A);

quicksort(p, q, A);

quicksort(q+1, r, A);

}

}

   

O vetor A[6..8] particionado

8 9 11

6 7 8

8 9 11

6 7 8

   

O pequeno...

void quicksort(int p, int r, int A[]){

if (p<r){

q = particao(p=6, r=8, A);

quicksort(p=6, q=7, A);

quicksort(q+1=8, r=8, A);

}

}

Vamos focar AQUI!!

   

O vetor A[6..7] agora

8 9

6 7

   

O pequeno código do QuickSort

void quicksort(int p, int r, int A[]){

if (p<r){

q = particao(p=6, r=7, A);

quicksort(p, q, A);

quicksort(q+1, r, A);

}

}

   

O vetor A[6..7] particionado

8 9

6 7

   

O pequeno código do QuickSort

void quicksort(int p, int r, int A[]){

if (p<r){

q = particao(p=6, r=7, A);

quicksort(p=6, q=6, A);

quicksort(q+1=7, r=7, A);

}

}

   

A função de partionamento

int particao(int p, int r, int A[]){

q = (p+r)/2;

pivo = A[q];

i=p-1; j=r+1;

faça{

faça{

i++;

}enquanto( pivo > A[i] );

faça{

j--;

}enquanto( pivo < A[j] );

se ( i < j )

troca(&A[i], &A[j]);

}enquanto( i < j );

}

   

Análise do Algoritmo● Vantagens:

– Faz ordenação “no local”;

– Tem tempo O(nlog(n));● Divide o problema em dois;● Altura da árvore de recursão igual

altura da árvore binária O(log(n));● Leva O(n) para particionar o vetor.

● Desvantagens:– Sua implementação é delicada;

Questões