15
Programação II Ordenação (sort) Bruno Feijó Dept. de Informática, PUC-Rio

Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

Programação II

Ordenação

(sort)

Bruno Feijó

Dept. de Informática, PUC-Rio

Page 2: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

Quick Sort(Ordenação Rápida)

Page 3: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

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 vetor

se n ≤ 1 então retorna

faz PARTIÇÃO com pivô x (i.e. coloca x no lugar certo)

quicksort do subvetor à esquerda de x

quicksort 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

Page 4: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

Algoritmo Quick Sort (recursivo) - CRESCENTE

25 48 37 12 57 86 33 92

a b

a b

troca e incr/decr12 48

a

b não troca nem in/decr

ab

troca pivô12 25 37 48 57 86 33 92

12

25 37 57 86 33 92xa b

a b

a b

b

...

a

va x vb x

se 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ção correta

de x

Subvetor à esq Subvetor à dir

0 a

b n - a

repete processo para cada subvetor

caminham

enquanto

decr b se vb x

incr 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 b

troca pivô x com vbquicksort(b, subvetor esquerdo)quicksort(n-a, subvetor direito)

Para a PARTIÇÃO, podemos ir caminhando com

os índices do vetor:

fica

repetindo

até que

PA

RT

IÇÃ

O

a para b para

Page 5: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

Código Quick Sort

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 vb

quicksort(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]);

}

Part

ição

CRESCENTE

Page 6: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

Generalizando o Algoritmo Quick Sort - Crescente

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 CRESCENTE seria:

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 !):

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]);

}

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

≤ 5 5

2

static int cmpInt(int x, int y)

{

return x > y ;

}

Elementos à

direita atendem

ao critério

Elementos à

esquerda NÃO

atendem ao critério

Geralmente definimos

a função auxiliar como sendo static.

Função static é

invisível fora do

arquivo no qual é

declarada.

O que é útil em módulos.

Page 7: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

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 x, int y)

{

return x < y ;

}

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]);

}

Generalizando o Algoritmo Quick Sort - Decrescente

Elementos à

direita atendem

ao critério

Elementos à

esquerda NÃO

atendem ao critério

Page 8: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

Template

void qsortTipo(int n, Tipo * v) // Ex: Tipo= int, Tipo= float, Tipo= Aluno *

{

Tipo x = v[0];

Tipo temp;

int a = 1, b = n-1;

if (n<=1) return;

do

{ while (a < n && !cmpFunction(v[a],x))

a++;

while (cmpFunction(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;

qsortTipo(b,v);

qsortTipo(n-a,&v[a]);

}

static int cmpFunction(Tipo x1, Tipo x2)

{

// Criterio que retorna verdadeiro ou falso

}

Função critério

de ordenação

Pode ser um critério simples (p.ex., se for vetor de inteiros) ou

um critério composto se for uma estrutura: p.ex., primeiro ordena

crescente pelo peso e depois crescente pela idade. Neste caso,

o critério é uma expressão booleana:

pesox1 > pesox2 || (pesox1 == pesox2 && idadex1 > idadex2)

Page 9: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

Exercício 1 – Ordenar vetor de floats

Escreva um programa completo que ordena CRESCENTEMENTE um vetor de

floats através do Quick Sort (e usando função de comparação). Depois indique a

mudança para a ordenação DECRESCENTE.

Page 10: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

Solução Exercício 1 – Vetor de floats

#include <stdio.h>int cmpFunction(float x1, float x2) // funcao criterio de ordenacao{

return x1 < x2; // Decrescente, e return x1 > x2; se Crescente}void qsortFloat(int n, float * v){

float x = v[0];float temp;int a = 1, b = n - 1;if (n <= 1) return;do{ while (a < n && !cmpFunction(v[a], x))

a++;while (cmpFunction(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;qsortFloat(b, v);qsortFloat(n - a, &v[a]);

}

printArray(float * v, int n){

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

printf("%.1f\n", v[i]);}

int main(void){

float vTemp[] = { 40.0, 15.0, 25.0, 30.0, 10.0 };int n = 5;qsortFloat(n, vTemp);printArray(vTemp, n);return 0;

}

Page 11: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

Exercício 2 – Ordena vetor de ponteiros para Dados

struct dados

{

int idade;

int peso;

};

typedef struct dados Dados;

Escreva programa completo, em módulos, que ordena um vetor de ponteiros para

estrutura Dados através do Quick Sort (e usando função de comparação), de acordo

o seguinte critério: primeiro em ordem crescente da idade e depois em ordem

crescente 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};

Faça a implementação em módulos com: dados.h, dados.c e testeDados.c.

Page 12: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

qsort – Quick Sort da Biblioteca C

Page 13: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

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 *))

Page 14: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

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éricos

n: número de elementos do vetor

tam: 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 == b

const é 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;

else

return 0;

}

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

Page 15: Programação II Ordenação (sort)bfeijo/prog2/ProgII_Sort_Part01_semGabaritoEx2.pdf · Algoritmo Quick Sort (recursivo) O algoritmo de Quick Sort foi desenvolvido por Sir Charles

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;

else

return 0;

}

void QsortPessoa(int n, Pessoa ** v)

{

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

}