Programação II

Ordenação(sort)

Bruno FeijóDept. de Informática, PUC-Rio

Quick Sort(Ordenação Rápida)

Algoritmo Quick Sort (recursivo)O algoritmo de Quick Sort foi desenvolvido por Sir Charles Hoare (Tony Hoare), em 1960, aos 26 anos.Suponha que você sabe colocar um dos elementos x do vetor (por exemplo, o primeiro) numa posição tal que todos os elementos antes são menores ou iguais a x e todos os elementos depois dele são maiores (note que, nesta tarefa, não importa se alguns elementos trocam de posição):

n elementos

5 4 3 7 1 2 6 9 54 31 7 6 9

x x

≤ x > x

≤ 5 > 5

2

Vamos denominar o elemento x escolhido de pivô e chamar esta etapa da ordenação de PARTIÇÃO. Neste caso, se você souber ordenar o subvetor esquerdo e o subvetor direito, você terá o vetor inicial completamente ordenado! Isto nos leva a definir uma função recursiva quicksort na qual o caso-base é um vetor com 1 ou nenhum elemento (e, neste caso, nada é preciso fazer) e o caso geral é fazer a partição seguida da chamada da função para o subvetor esquerdo e da chamada da função para o subvetor direito:

quicksort do vetorse n>1 então

PARTIÇÃO com pivô xquicksort do subvetor à esquerda de xquicksort do subvetor à direita de x

No próximo slide estão sugeridos um processo simples e direto para a PARTIÇÃO e uma maneira de se referenciar aos subvetores à esquerda e à direita de x.

n = 8

Algoritmo Quick Sort (recursivo)25 48 37 12 57 86 33 92

a ba b

troca e incr/decr12 48ab não troca nem in/decrab

troca pivô12 25 37 48 57 86 33 9212

25 37 57 86 33 92xa b

a b

a b

b

...a

va > x vb ≤ xse a < b, troca e incrementa

se b < a, troca pivô x com vb

vb x va

região dos ≤ x região dos > x

posiçãocorretade x

subvetor subvetor

0 a

b n - a

repete processo para cada subvetor

caminhamaté que

decr b se vb > xincr a se va ≤ x

bbb

quicksort(n,v)se n <= 1 então retornax = v0 a = 1 b = n-1faça

enquanto a < n e va ≤ xa = a + 1

enquanto vb > xb = b - 1

se a < b então troca va com vb e a= a+1 e b= b-1enquanto a ≤ btroca pivô x com vbquicksort(b, subvetor esquerdo)quicksort(n-a, subvetor direito)

Para a PARTIÇÃO, podemos ir caminhando comos índices do vetor:

ficarepetindoaté que

Código Quick Sort

25 48 37 12 57 86 33 92a ba b12 48

abab

12 25 37 48 57 86 33 9212

25 37 57 86 33 92

quicksort(n,v)se n <= 1 então retornax = v0 a = 1 b = n-1faça

enquanto a < n e va ≤ xa = a + 1

enquanto vb > xb = b - 1

se a < b então troca va com vb e a= a+1 e b= b-1enquanto a ≤ btroca pivô x com vbquicksort(b, subvetor esquerdo)quicksort(n-a, subvetor direito)

void quicksort(int n, int * v){

int x = v[0];int temp;int a = 1;int b = n-1;if (n<=1)

return;do{

while (a < n && v[a] <= x)a++;

while (v[b] > x)b--;

if (a < b){

temp = v[a];v[a] = v[b];v[b] = temp;a++;b--;

}} while (a <= b);v[0] = v[b];v[b] = x;quicksort(b,v);quicksort(n-a,&v[a]);

}

Parti

ção

Generalizando o Algoritmo Quick Sort

O desenvolvimento apresentado nos slides anteriores refere-se à ordenação em ordem CRESCENTE de um vetor de INTEIROS. Uma primeira generalização é perceber que a partição divide o vetor em elementos que atendem o critério de ordenação à direita do pivô e elementos que NÃO atendem à esquerda. Por exemplo, a ilustração da partição para uma ordem DECRESCENTE seria:

5 4 3 7 1 2 6 9 59 67 2 3 4

≥ 5 < 5

1

O critério de ordenação pode ser definido numa função auxiliar de comparação que é usada em dois momentos no algoritmo de quick sort, sendo um momento a negação do outro (operador !):

static int cmpInt(int a, int b){

return a < b;}

void quicksort(int n, int * v){

int x = v[0];int temp;int a = 1;int b = n-1;if (n<=1)

return;

do{

while (a < n && !cmpInt(v[a],x))a++;

while (cmpInt(v[b],x))b--;

if (a < b){

temp = v[a];v[a] = v[b];v[b] = temp;a++;b--;

}} while (a <= b);v[0] = v[b];v[b] = x;quicksort(b,v);quicksort(n-a,&v[a]);

}

Exercícios

struct dados{

int idade;int peso;

};typedef struct dados Dados;

[1] Escreva programa completo que ordena um vetor de ponteiros paraestrutura Dados através do Quick Sort (e usando função de comparação), de acordoo seguinte critério: primeiro em ordem crescente da idade e depois em ordemcrescente do peso.

Sugestão para teste:Dados tab[] = {{20,50},{10,30},{25,40},{18,65},{10,40},{18,60}};Dados * v[] = {tab,tab+1,tab+2,tab+3,tab+4,tab+5};

qsort – Quick Sort da Biblioteca C

Ponteiros para Funções

• Em C é possível definir ponteiros para funções que podem ser colocados em vetores, passados para funções e retornados por funções

• No exemplo a seguir, a função opera(m, x, y, func) recebe um ponteiro de função como um de seus argumentos (func) e retorna m × func(x,y). Devemos notar que o nome da função mult é um ponteiro quando escrevemos opera(2,3,5,mult);

#include <stdio.h>

int mult(int x,int y);int soma(int x, int y);int opera(int m, int x, int y, int(*func)(int, int));

int main(void){

int a, b;a = opera(2,3,5,mult);b = opera(2,3,5,soma);printf("%d %d\n",a,b);return 0;

}

int mult(int x,int y){

return x*y;}

int soma(int x, int y){

return x+y;}

int opera(int m,int x,int y,int(*func)(int, int)){

return m*func(x,y);}

Saída:

30 16

Se argumentos são ponteiros, usamos const quando queremos garantir que a função func não modificará os valores que são apontados: int(*func)(const int *, const int *))

Quick Sort da stdlib do C

void qsort(void * v, int n, int tam, int (*cmp)(const void *, const void *));v: vetor de ponteiros genéricosn: número de elementos do vetortam: tamanho em bytes de cada elemento (use sizeof para especificar)cmp: ponteiro para função que compara elementos genéricos

int nome(const void * a, const void * b);deve retornar <0 se a<b, >0 se a>b e 0 se a == bconst é para garantir que a função não modificará os valores dos elementos

static int compFloat(const void * a, const void * b){

/* converte os ponteiros genericos */float * aa = (float *)a;float * bb = (float *)b;/* faz a comparacao com (*aa) e (*bb) retornando -1,0, ou 1 */if (*aa > *bb) // atenção para o *

return 1;else

if (*aa < *bb)return -1;

elsereturn 0;

}

chamada: qsort(v,N,sizeof(float),compFloat); // N é o tamanho de v

Exemplo Quick Sort da stdlib

#include <stdlib.h>int main(void){

...Pessoa tab[] = {{"Diana Maria",22}, ...};Pessoa * v[] = {tab,tab+1, ...};...QsortPessoa(n,tabPessoa); // ordenacao com Quick Sort...

}

int compPessoa(const void * a, const void * b){

Pessoa ** aa = (Pessoa **)a;Pessoa ** bb = (Pessoa **)b;int cmp = strcmp((*aa)->nome,(*bb)->nome);if (cmp>0 || (cmp==0 && ((*aa)->idade>(*bb)->idade)))

return 1;else

if (cmp<0 || (cmp==0 && ((*aa)->idade<(*bb)->idade)))return -1;

elsereturn 0;

}

void QsortPessoa(int n, Pessoa ** v){

qsort(v,n,sizeof(Pessoa *),compPessoa);}

Tópicos Extras

Bubble Sort

Bubble Sort – Ordem Crescente

• Apenas de interesse didático e de referência• A idéia é ir comparando dois vizinhos e trocando o menor pelo maior até

que o maior de todos fica no final (como se o maior fosse uma “bolha” que sobe até o topo)

0 1

1 2

j j+1

...

...

0 1

j j+1...

passo 1 passo 2 passo 3 ...

1 2 ...

Este é o maior de todos Este é o segundo maior de todos

Exemplo Bubble Sort – Passo 1 e Passo 2

25 48 37 12 57 86 33 92 25x4825 48 37 12 57 86 33 92 48x37 troca25 37 48 12 57 86 33 92 48x12 troca25 37 12 48 57 86 33 92 48x5725 37 12 48 57 86 33 92 57x8625 37 12 48 57 86 33 92 86x33 troca25 37 12 48 57 33 86 92 86x9225 37 12 48 57 33 86 92 final do passo 1

o maior elemento, 92, já está na sua posição final

25 37 12 48 57 33 86 92 25x3725 37 12 48 57 33 86 92 37x12 troca25 12 37 48 57 33 86 92 37x4825 12 37 48 57 33 86 92 48x5725 12 37 48 57 33 86 92 57x33 troca25 12 37 48 33 57 86 92 57x8625 12 37 48 33 57 86 92 final do passo 2

o segundo maior elemento, 86, já está na sua posição final

n = 8 elementos

n –

1co

mpa

raçõ

es (i

.e.7

)n

–2

com

para

ções

(i.e

.6)

Bubble Sort – Passo 3 e Passo 4

25 12 37 48 33 57 86 92 25x12 troca12 25 37 48 33 57 86 92 25x3712 25 37 48 33 57 86 92 37x4812 25 37 48 33 57 86 92 48x33 troca12 25 37 33 48 57 86 92 48x5712 25 37 33 48 57 86 92 final passo 3

Idem para 57.

12 25 37 33 48 57 86 92 12x2512 25 37 33 48 57 86 92 25x3712 25 37 33 48 57 86 92 37x33 troca12 25 33 37 48 57 86 92 37x4812 25 33 37 48 57 86 92 final do passo 4

Idem para 48. Não irá trocar mais.Veja isto no próximo passo

n –

3(=

5)

n –

4(=

4)

Bubble Sort – Passos 5, 6 e 7

12 25 33 37 48 57 86 92 12x2512 25 33 37 48 57 86 92 25x3312 25 33 37 48 57 86 92 33x3712 25 33 37 48 57 86 92 final do passo 5

Idem para 37.

12 25 33 37 48 57 86 92 12x2512 25 33 37 48 57 86 92 25x3312 25 33 37 48 57 86 92 final do passo 6

Idem para 33.

12 25 33 37 48 57 86 92 12x2512 25 33 37 48 57 86 92 final do passo 7

Idem para 25 e, conseqüentemente, 12.

12 25 33 37 48 57 86 92 final da ordenação

Passo 5 sem troca!Os dois próximospassos são desperdícios!

n –

5(=

3)

n –

6(=

2)

n –

7(=

1)

Algoritmo de Bubble Sort – Solução Conceitual

bolhaInt(vetor v de inteiros, n)i = n-1para cada i, enquanto i>0

haTroca= 0 // p/rastrear trocasj = 0para cada j, enquanto j<i

se compInt(vj,vj+1) é VERDADE

troca vj e vj+1haTroca= 1; // marca troca

incrementa j de 1if haTroca é zero

retornadecrementa i de 1

DICAS PARA A IMPLEMENTAÇÃO:- Use for para os loops. - Para trocar vj e vj+1 use uma variável auxiliar.- A função de comparação deve retornar VERDADE (valor diferente de zero) ou FALSO (zero). - Os argumentos desta função são do mesmo tipo do vetor.- Geralmente definimos esta função como sendo static . Função static é invisível fora do arquivo no qual é declarada.- Este algoritmo é geral. Só muda o que está em vermelho e itálico.

O critério de ordenação é definido dentrodesta função compInt que compara doiselementos do vetor (no caso, 2 inteiros).

Ordem Crescente:static int compInt(int a, int b){

return a > b;}

Ordem Decrescente:static int compInt(int a, int b){

return a < b;}

Código bolhaInt – Ordem Crescentevoid bolhaInt(int * v, int n){

int i,j,haTroca;int temp;for (i=n-1;i>0;i--){

haTroca= 0;for (j=0;j<i;j++){

if (compInt(v[j],v[j+1])){

temp = v[j];v[j] = v[j+1];v[j+1] = temp;haTroca= 1;

}}if (haTroca==0)

return;}

}

bolhaInt(vetor v de inteiros, n)i = n-1para cada i, enquanto i>0

haTroca= 0j = 0para cada j, enquanto j<i

se compInt(vj,vj+1) é VERDADE

troca vj e vj+1haTroca= 1; // marca troca

incrementa j de 1if haTroca é zero

retornadecrementa i de 1

static int compInt(int a, int b){

return a > b;}

Para outros tipos, só muda o que estáem vermelho e itálico

troca

Depois faça para vetor de strings(bolhaStr), ordem crescente.Resposta no próximo slide!

Código bolhaStr – Ordem Crescente

void bolhaStr(char ** v, int n){

int i,j,haTroca;char * temp;for (i=n-1;i>0;i--){

haTroca= 0;for (j=0;j<i;j++){

if (compStr(v[j],v[j+1])){

temp = v[j];v[j] = v[j+1];v[j+1] = temp;haTroca= 1;

}}if (haTroca==0)

return;}

}

int main(void){

char * v[] = {"daniel","ana",...,};...bolhaStr(tab, N);...

static int compStr(char * a, char * b){

return (strcmp(a,b) > 0);}

trocastrcmp(x,y) é uma função da biblioteca de stringsque retorna o seguinte:< 0 se o primeiro caractere que não casa tem um

valor mais baixo em x do que em y0 se os conteúdos dos dois strings são iguais

>0 se o primeiro caractere que não casa tem umvalor mais alto em x do que em y

Por ex.: strcmp("daniel","ana") retorna > 0strcmp("Ana","ana") retorna < 0 (porque'A' é menor que 'a' na tabela ASCII

Exercícios

typedef struct pessoa Pessoa;struct pessoa{

char * nome;int idade;

};

[1] Escreva programa completo, em módulos, que ordena um vetor de ponteiros paraestrutura Pessoa:

usando o seguinte critério: ordem crescente de nome e ordem crescente de idade(note que há 3 Diana Maria de idades diferentes).

Obs1: evite ninhos de if e use expressões booleanas (com ||, && e !).Obs2: para montar o vetor, declare e inicialize vetores:

Pessoa tab[] = {{"Diana Maria",22}, ...};

Pessoa * v[] = {tab,tab+1, ...};

Obs3: faça uma função auxiliar imprimeVetPessoa que imprime o vetor

Diana Maria 22Beatrice Dante 30Ada Eva 30Diana Maria 26Beatrice Dante 29Helena Troia 25Diana Maria 20Beatrice Dante 25

Código bolhaPessoa

void bolhaPessoa(Pessoa ** v, int n){

int i,j,haTroca;Pessoa * temp;for (i=n-1;i>0;i--){

haTroca= 0;for (j=0;j<i;j++){

if (compPessoa(v[j],v[j+1])){

temp = v[j];v[j] = v[j+1];v[j+1] = temp;haTroca= 1;

}}if (haTroca==0)

return;}

}

struct pessoa{

char * nome;int idade;

};typedef struct pessoa Pessoa;

static int compPessoa(Pessoa * a, Pessoa * b){

int cmp = strcmp(a->nome,b->nome);return (cmp > 0 || (cmp==0 && (a->idade)>(b->idade)));

}

int main(void){

...bolhaPessoa(v, N);...trocaC

Algoritmo Genérico

void bolhaGen(void * v, int n, int tam, int(*comp)(const void *, const void *)){

int i,j,haTroca;void * p1;void * p2;for (i=n-1;i>0;i--){

haTroca= 0;for (j=0;j<i;j++){

p1 = acessa(v,j,tam);p2 = acessa(v,j+1,tam);if (comp(p1,p2))

troca(p1,p2,tam);haTroca= 1;

}if (haTroca==0)return;

}}

static void * acessa(void * v,int i,int tam){

char * t = (char *)v; // char = 1 bytet += tam*i;return (void *)t;

}

static void troca(void * a, void * b, int tam){

char temp;char * v1 = (char *)a; // troca byte a bytechar * v2 = (char *)b;int i;for (i=0; i<tam; i++){

temp = v1[i];v1[i] = v2[i];v2[i] = temp;

}}

static int compPessoaGen(const void * a, const void * b){

Pessoa ** aa = (Pessoa **)a;Pessoa ** bb = (Pessoa **)b;int cmp = strcmp((*aa)->nome,(*bb)->nome);return (cmp>0 || (cmp==0 && (*aa)->idade > (*bb)->idade));

}

void ordenaPessoa(int n, Pessoa ** v){

bolhaGen(v,n,sizeof(Pessoa *),compPessoa);}

Assunto Avançado

Selection Sort

(Ordenação por Seleção)

Conceito do Selection Sort – Ordem Crescente

- Supomos que o maior elemento (max) é o que está na posição 0

- A partir da posição 1, procuramos se há alguém maior (max) do que o valor na posição 0

- trocamos este máximo pelo último

- Deslocamos o fim do vetor para 1 (uma) posição à esquerda

- Repetimos o processo

Note que o processo vai dividindo o vetor em uma parte ordenada e outra não ordenada. fim

fim

fim

fim

fim

Um processo equivalenteé trabalhar com o mínimoe trocar com o primeiro.Neste caso, o vetor ordenado vai se construindo à esquerda.

Selection Sort

void selectionInt(int * v, int n){

int fim, iMax, i;int temp;for (fim = n-1; fim > 0; fim--){

iMax= 0; /* indice do maior*/for (i=1;i<=fim;i++)

if ( v[i]> v[iMax] )iMax = i;

temp = v[fim];v[fim] = v[iMax];v[iMax] = temp;

}

troca

critério if ( compInt(v[i], v[iMax]) )

static int compInt(int a, int b){

return a > b;}

Ou usando uma funçãopara um critério genérico

Implemente a versão que trabalha com o mínimo!

Complexidade

(assunto avançado)

Complexidade de Tempo

• O tempo gasto por um algoritmo é função do tamanho n da entrada de dados e depende do número de operações que cada passo do algoritmo executa.

• T(n) indica a dimensão este tempo de uma forma geral (e independente de hardware)• No caso do algoritmo Bubble, numa análise aproximada, o passo 1 faz n-1

comparações, o passo 2 faz n-2 comparações, ... . De maneira aproximada, temos:

• Isto é igual à soma de uma série aritmética de m termos, onde m = n-1:

• Para grandes valores de n (n → ∞), esta função é limitada pela função bn2, onde b é uma constante, i.e.:

• Como regra geral, o termo de mais alta ordem de uma função domina sua taxa de crescimento (i.e., na prática, suprimimos constantes multiplicativas e termos de baixa ordem para descrever o comportamento limite de uma função)

• Dizemos, então, que o algoritmo Bubble tem uma complexidade de tempo quadráticae usamos a notação do Big O para indicar este limite superior: O(n2)

12)2()1()( +++−+−= nnnT

(n-1) + (n-2) + ... + 2 + 1 Série Aritmética Sm = m(a1 + am)/2

am a1 m = n-1 Sm = n(n-1)/2

nnnnnT21

212/)1()( 2 −=−=

22

21

21)( bnnnnT ≤−=

Complexidades Comuns (notação Big O)

Notação Big OO(1) Tempo constanteO(log n) Tempo logarítmicoO(n) Tempo linearO(n log n) Tempo loglinear (ou quaselinear)O(n2) Tempo quadrático

Limite n2

nnnT21

21)( 2 −=

Quase linear

n

Diferença entre n e log n

36 seg100 anos94 608 000 000301 ano946 080 000211 mês2 592 000161 dia86 400121 h3 600910 min60061 min60

3 seg10 seg10O(log n)O(n)tamanho

Outras Considerações sobre Complexidade

• Na análise de complexidade, procuramos o “Pior Caso”, o “Melhor Caso” e o “Caso Médio”

– Bubble Sort tem o “Melhor Caso” quando a lista já está ordenada. Neste caso, a complexidade de tempo é O(n)

– O “Caso Médio” para Bublle Sort também é O(n2)• Entre algoritmos de mesma complexidade, há diferenças em eficiência

– Por exemplo, Selection Sort é similar ao Bubble Sort e ambos tem O(n2), isto é: ele faz o mesmo número de comparações que o Bubble. Entretanto, Selection Sort tem um menor número de comparações e tende a ser aproximadamente 2 vezes mais eficiente. Eficiência não é a mesma coisa que complexidade!

• Em geral– uma única operação (ou comando) tem um tempo de execução de O(1)– Um loop (laço) que é repetido n vezes tem O(n)– Dois laços aninhados (nested loops) indo de 1 a n tem O(n2)

• Se um algoritmo tem vários passos de complexidades diferentes, a complexidade do algoritmo como um todo é dado pelo máximo.

– Por exemplo, um algoritmo com 3 passos de O(n2), O(n2) e O(n), tem complexidade O(n2)

Complexidade do Quick Sort – Pior Caso

Esta etapa (que caminha pelo vetor, compara e troca valores) consome um tempo cn (*). As outras duas etapas são as chamadas recursivas. Temos, então:

(*) o maior valor de c seria para um código que percorresse uma vez o vetor, guardando os elementos menores do que x (e opróprio x) em um vetor temporário, percorresse novamente o vetor, guardando os elementos maiores do que x, efinalmente copiasse o vetor temporário para o vetor original. Neste caso, o tempo seria 4n (i.e. c = 4).

A primeira etapa do algortimo de sort é colocar o pivô x na posição que divide o vetor entre os elementosmenores que x e os maiores que x :

x

k n-k

cnknTkTnT +−+= )()()(PIOR CASO: pivô x é o menor, em cada passo. Neste caso, k =1 e n-k = n-1

passo 1: cnnTTnT +−+= )1()1()(

passo 2: )1()1(2)2(])2()1([)1()( nncTnTcncnnTTTnT +−++−=++−++=

passo 3: )12()1(3)3()1()1(2)]2()3()1([)( nnncTnTnncTncnTTnT +−+−++−=+−++−+−+=

passo i: )11()1()()( nninciTinTnT +−+++−++−=

...

e considerando que vamos até n− i=1, i.e. i = n − 1, temos: )2)(1()1()( +−+= nncnTnTA soma da série aritmética de i termos n− i+1,...,n−1,n é: 2/)12( iniSi −+=

A complexidade é, portanto: ( )22)2)(1()1()( nOdnnncnTnT →≤+−+=O mesmo vale para pivô x sendo o maior.

Complexidade do Quick Sort – Melhor Caso

MELHOR CASO: pivô x divide vetor em duas partes iguais, em cada passo. Neste caso, k =n/2 e n-k = n/2

passo 1: cnnTcnnTnTnT +=++= )2/(2)2/()2/()(

passo 2: cnnTcncnnTnT 2)2/(2]2/)4/(2[2)( 22 +=++=

passo 3: cnnTcncnnTnT 3)2/(22]2/)2/(2[2)( 33232 +=++=

passo i: icnnTnT ii += )2/(2)(...

considerando que vamos até n/2i = 1, i.e. n = 2i , ou seja, i = log n, temos:

Podemos também provar que no CASO MÉDIO (para todas as possíveis configurações de pivô), quick sort tem uma complexidade de tempo de O(n log n).

( )nnOndnncnnTnT logloglog)1()( →≤+=

Melhoras no algoritmo podem ser feitas no sentido de reduzir a chance de ocorrer o pior caso.Uma idéia é pegar o pivô aleatóriamente cada vez. Outra idéia é encontrar a mediana do vetora ser ordenado cada vez, e usar a mediana como pivô (isto tem um custo extra alto de complexidadeconstante, mas que pode compensar ). Veja também o método baseado em 3 medianas.Selection Sort pode ser mais vantajoso para listas pequenas (≤ 30) ou quase ordenadas.

Ironicamente, vetores já ordenados (ou quase ordenados) e com o pivô sendo o primeiro (ou o último) elemento representam situações tipo “pior caso”.