Métodos de Ordenação

Desempenho, Método de Shell, Quicksort

Análise de Desempenho

• A análise de desempenho visa determinar uma função (f) que permita computar o tempo gasto por um algoritmo.

• F é função do tamanho da entrada do algoritmo

Exemplo

Determinar a função de desempenho da função troca vetores:

void trocavetores(int a[],int b[], int n) {

int i;

for(i=0;i<n;i++)

troca(&a[x],&b[x]);

}

Desempenho

1. Atribuir custo às operações usadas no algoritmo:

void trocavetores(int a[],int b[], int n) {

int i;

n for(i=0;i<n;i++)

1 troca(&a[x],&b[x]);

}

2. Considerar os loops multiplicando os custos:

f(n) = n * 1

Desempenho

• Considerar só as operações relevantes para o desempenho. Operações podem ser desprezadas se forem insiginificantes com relação as operações relevantes:

void trocavetores(int a[],int b[], int n) {

int i,x,y;

n for(i=0;i<n;i++){

0 x=a[i];

0 y=b[i]

1 troca(&x,&y);

0 a[i]=x;

0 b[i]=y;

}

f(n) = n * 1

Desempenho

• Um loop dentro de outrovoid leMatrizQuadrada(int m[MAX][MAX], int n, FILE *arq){

int i,j;

n for(i=0;i<n;i++) {

n for(j=0;j<n;j++) {

1 fscanf(arq,”%d”, &m[i][j]);

}

}

f(n) = n*n*1 = n2

Desempenho

• Em algoritmos de ordenação f é determinada em função do tamanho do vetor

• As operações relevantes são as comparações e trocas

Desempenho método da seleção

algoritmo seleção (int a[], int n){L1 Para i da primeira posição até a penúltima faca 0 mínimo = i L2 para j da posição seguinte a i até a ultima

posição faça 1 se (a[j] < a[mínimo] minimo =j; fim para 1 troca(a[mínimo],a[i]); fim parafim algoritmoL1 = n-1L2 = (n-1) + (n-2) + .. + 1 = n*(n-1)/2 F(n) = (n*(n-1)/2)*1 + (n-1)*1F(n) = n*(n-1)/2 + (n-1)

Desempenho Método da InserçãoAlgoritmo insercao(int A[], int n)

(n-1) para j do segundo elemento até o último faça

x = A[j];

i=j-1;

(???) enquanto (i >= 0 e A[i] > x) faça

A[i+1]=A[i];

i = i-1;

fim enquanto

A[i+1]=x;

fim para

fim algoritmo

1

Desempenho Método da Inserção

• Em algoritmo como o método da inserção (devido ao loop mais interno) o desempenho não depende somente do tamanho da entrada, depende também do formato da entrada.

• Neste caso o formato é: o vetor já está ordenado, está parcialmente ordenado, invertido, formato aleatório.

• Nestes casos temos que considerar:– O melhor caso– O pior caso– O caso médio

Desempenho Método da Inserção

• Calculando o custo do loop mais interno. Ci é o custo deste loop na i-ésima interação do loop mais externo:– Melhor caso: Ci(n) = 1,

– Pior caso: Ci(n) = i,

– Caso Médio: Ci(n) = 1 / i * (1 +2 + ...+ i) = (i+1)/2• Ex: i = 2, = ½ *(1+2), 50% de chance haver uma

interação e 50% de chance de haver duas interações.

Desempenho Método da Inserção

• F(n) = C2 + C3 + .. + Cn

• Calculando o valor de f, temos que considerar os 3 casos:– Melhor Caso: f(n) = (1 + 1 + .. + 1) = n-1– Pior caso: f(n) = (2 + 3 + 4 .. + n) = n2/2 + n/2 –1– Caso médio: f(n) = ½ (3 + 4 + .. n +1) = n2/4 + 3n/4

-1

Desempenho Método da Bolhaalgoritmo bolha ( int a[],int n)

L1 Para i do ultimo elemento até o segundo faça

L2 para j do segundo elemento até i faça

1 se (a[j-1]>a[j])

1 troca(&a[j-1],&a[j]);

}

Melhor caso: f(n) = n2/2

Pior caso: f(n) = 2 n2

Caso médio: f(n) = 5n2/2

Observação: Vejam a implementação do bolha em Assembly em http://pt.wikipedia.org/wiki/Bubble_sort#Assembly

Não é fácil programar em C?

Exercício

• Obter as expressões do pior, melhor e caso médio para o método da bolha.

Método de Shell (Shell Sort)

• Método inventado por Shell. • Consiste em aplicar o método de inserção em

elementos não adjacentes do vetor. • Algoritmo:

– Inicialmente, é determinada uma distância d. – Todos os elementos localizados no vetor separados

por uma distância d são ordenados. – A cada iteração a distância d é reduzida de acordo

com alguma seqüência. – Na ultima iteração esta distância é reduzida a 1. Este

passo corresponde ao método de inserção original.

Método de Shell

• Exemplo: – Vetor: [35,28,16,07,12,08,04] - – Seqüência de Distâncias: - {3,1}

35 28 16 07 12 08 04 35 está ordenado, 7 é comparado

07 28 16 35 12 08 04 {07,35} está ordenado, 4 é comparado

04 28 16 07 12 08 35 {04,07,35} está ordenado

04 28 16 07 12 08 35 28 está ordenado, 12 é comparado

04 12 16 07 28 08 35 {12,28} está ordenado

04 12 16 07 28 08 35 16 está ordenado, 35 é comparado

04 12 08 07 28 16 35 {08,16} está ordenado

Passo 2 : d =1 equivalente ao método da inserção

Método de ShellAlgoritmo shell(int A[], int n, int d) para j de d até o último elemento faça x = A[j]; i=j-d; enquanto (i >= 0 e A[i] > x) faça A[i+d]=A[i]; i = i-d; fim enquanto A[i+d]=x; fim para fim algoritmo

• Quando d = 1 equivale ao algoritmo de inserção:

Algoritmo insercao(int A[], int n) para j do segundo elemento até o último

faça x = A[j]; i=j-1; enquanto (i >= 0 e A[i] > x) faça A[i+1]=A[i]; i = i-1; fim enquanto A[i+1]=x; fim para fim algoritmo

Método de Shell

• O algoritmo ordena os elementos separados uma distância d.

• A distância d é dada por uma seqüência decrescente.

• Para cada valor de d chamamos o algoritmo shell

Exemplo:

shellSort1(int a[], int n) {

int d[2] = {3,1};

int p,nd =2;

for (p=0;p<nd;p++) {

shell(a,n,d[p]);

}

}

Método de Shell

• A seqüência {3,1} pode não ter eficiência para grandes vetores.

• Não existe uma seqüência ideal. • Donald Knuth mostrou empiricamente

que a seqüência ( 1, 4, 13, 40, 121, 364, 1093..) apresenta eficiência 20 % maior que outras seqüências.

Método de Shell

• Implementação da seqüência de Knuth:#define MAX xxxxx // tamanho máximo do vetorvoid shellsort2(int a[],int n) { int i,p=0, d[MAX/9]; if((n/9)<1){ // trata vetores < 9 p =1; d[0]=1; } else { // gera sequencia de knuth no vetor d for (i=1;i<=n/9;i=3*i+1) { d[p] =i; p++; } } for (i=p-1;i>=0;i--) { // executa shell printf("%d \n", d[i]); shell(a,n,d[i]); } }

Método Quicksort (QS)

• Baseado na estratégia Dividir para conquistar.

• Algoritmo:1. Inicialmente, o vetor a[0..n-1] é subdividido em

dois vetores – a[0..p] e a [ p+1 .. r] não vazios – cada elemento de a[0..p] é menor ou igual a cada

elemento de a[p+1..n-1]. – A[p] é chamado pivô da iteração. – O valor de p é escolhido arbitrariamente. Um escolha

trivial é o pivô central p = (esq + dir)/2

2. Os dois subvetores a[0..p] e a[p+1..n-1] são ordenados por chamadas recursivas do QS. Ou seja, repete-se o passo 1 para cada um dos subvetores, recursivamente.

Método Quicksort

• A operação que divide os elementos do vetor entre maiores e menores que o pivô é chamada de particionamento.

• Exemplo: a = { 12, 7, 3, 2, 10, 1, 0}, n =7 , n-1 = 6

particiona (a,0,6) - escolhe o pivô: q = (0+6)/2=3 a[q] = 2

troca 12 com 0

troca 7 com 1

troca 2 com 3

O vetor ficou: {0,1,2,3,10,7,12}

Repete o particionamento para a[0..2] e a[3..6]

Método Quicksort

a[0..2] = {0,1,2}

Particiona(a,0,2) pivô = 1

Não há trocas

a[3..6] = {3,10,7,12}

Particiona(a,3,6) pivô = q= (3+6)/2 = 4 a[4] = 10

Troca 10 com o 7

No final o vetor está ordenado:{0,1,2,3,7,10,12}

Método Quicksort

void particiona(int a[], int esq,int dir, int *pi, int *pj) {

int x, i,j;

i = esq; j = dir;

x = a[(i+j)/2]; // obtém o pivô desta partição

faça {

procuro por a[i] do lado esquerdo menor que o pivô

procuro por um a[j] do lado direito maior que o pivô

}

se i e j não se cruzarem eu encontrei elementos para trocar

troca(a[i],a[j]);

avanço o i para depois do elemento trocado

avanço o j para antes do elemento trocado

} enquanto(i< j);

retorno o i e o j para servirem de limites para as novas

partições

}

Método quicksortvoid particiona(int a[], int esq,int dir, int *pi, int *pj) { int x,i,j; i = esq; j = dir; x = a[(i+j)/2]; // obtem o pivo desta particao faça { // procuro a[i] > x a esquerda enquanto((x > a[i]) && (i<dir)) { i=i+1 } // procuro a[j] < x a direita enquanto ((x < a[j]) && (j>esq)){ j=j-1 } // se i < = j então eu achei os valores para trocar se(i<=j) { troca(&a[i],&a[j]); i=i+1; j=j-1; } } enquanto(i< j); // retorno os valores de i j *pi = i; *pj = j; }

Método quicksort ordenaQS(int a[], int esq, int dir) {

int i,j;

particiona(a, esq,dir, &i,&j)

se (esq<j)

ordenaQS(a,esq,j)

se (dir>i)

ordenaQS(a,i,dir)

}

quicksort(int a[],int n) {

ordenaQS(a,0,n-1)

}

Método quicksort

• Desempenho: – Melhor caso: n log( n )– Caso médio: n log( n )– Pior caso: n2

• Pesquisa sobre o desempenho do Quicksort,

• Fonte – livro referência - Nivio Ziviani – Projeto de algoritmos

– http://www.google.com