AED AlgoritmoseEstruturasde Dados LEEC -2005/2006

AEDAlgoritmos e Estruturas de Dados

LEEC - 2005/2006

Algoritmos de Ordenação – 1ª parte

AED (IST/DEEC) 2

Porquê estudar algoritmos elementares(de ordenação)

• Razões de ordem prática– Fáceis de codificar e por vezes suficientes– Rápidos/Eficientes para problemas de dimensão média e por vezes os

melhores em certas circunstâncias

• Razões pedagógicas– Bom exemplo para aprender terminologia, compreender contexto dos

problemas e bom princípios para desenvolvimento de algoritmos mais sofisticados

– Alguns são fáceis de generalizar para métodos mais eficientes ou para melhorar o desempenho de outros algoritmos

• Importante para compreensão das regras de "funcionamento"

AED (IST/DEEC) 3

Contexto e regras básicas [1]

• Objectivo– Estudar métodos de ordenação de ficheiros de dados em que cada

elemento (item) é caracterizado por uma chave ("key")– Chaves são usadas para controlar a ordenação– objectivo é rearranjar os dados de forma a que as chaves estejam

ordenadas de forma pré-definida (numérica ou alfabética, por exemplo)

• Opções em termos de implementação– macros ou subrotinas/funções?

• compromisso entre desempenho, generalidade e simplicidade• utilizaremos uma mistura de ambos

AED (IST/DEEC) 4

Contexto e regras básicas [2]• Metodologia

– características específicas de cada item ou chave podem ser diferentes mas conceito abstracto é o mais importante

– começaremos por estudar ordenação em tabelas– utilizaremos operações abstractas nos dados: comparação, troca– alterar items para outro tipo (ex: vírgula flutuante) é simples

• Tempo de execução usualmente proporcional ao número de comparações número de movimentações/trocas (ou ambos)

typedef int Item;#define key(A) (A)#define less(A, B) (key(A) < key(B))#define exch(A, B) {Item t = A; A = B; B = t; }#define compexch(A, B) if (less(B,A)) exch(A, B)

AED (IST/DEEC) 5

Nomenclatura [1]• Tipos de Algoritmos de Ordenação

– não adaptativos: sequência de operações independente da ordenaçãooriginal dos dados

• interessantes para implementação em hardware– adaptativos: sequência de operações dependente do resultado de

comparações (operação "less")• a maioria dos que estudaremos

• Parâmetro de interesse é o desempenho, i.e. tempo de execução– algoritmos básicos: N2 para ordenar N items

• mas por vezes os melhores para N pequeno– algoritmos avançados: N log N para ordenar N items

• Olharemos também para os recursos de memória necessários– ordenação "in-place" ou utilizando memória adicional

AED (IST/DEEC) 6

Nomenclatura [2]

• Definição: um algoritmo de ordenação é dito estável se preserva a ordem relativa dos items com chaves repetidas

ex: ordenar lista de alunos por ano de graduação quando esta jáestá ordenada alfabeticamente por nome– é usualmente possível estabilizar um algoritmo alterando a sua

chave (tem custo adicional)– algoritmos básicos são quase todos estáveis, mas poucos

algoritmos avançados são estáveis

AED (IST/DEEC) 7

Nomenclatura [3]

• Definição: um algoritmo de ordenação é dito interno, se o conjunto de todos os dados a ordenar couber na memória; caso contrário é dito externo

ex: ordenar dados lidos de tape ou disco é ordenação externa

• Distinção muito importante:– ordenação interna pode aceder a qualquer dado facilmente– ordenação externa tem de aceder a dados de forma sequencial (ou

em blocos)

• Vamos estudar fundamentalmente ordenação interna

AED (IST/DEEC) 8

Nomenclatura [4]

• Definição: um algoritmo de ordenação é dito directo se osdados são acedidos directamente nas operações de comparação e troca; caso contrário é dito indirecto

• Exemplo de algoritmo indirecto:– se a chave for pequena e cada dado for "grande”

• (por exemplo o nome completo de um aluno, mais morada, número de BI, etc)

• nestes casos não convém estar a trocar os elementos– é dispendioso

• basta trocar a informação correspondente aos seus índices– tabela de índices/ponteiros em que o primeiro indica o menor elemento, etc

AED (IST/DEEC) 9

• Mesmo programa, diferentes drivers para diferentes algoritmos:

Para cada algoritmo, "sort" tem nome apropriado

Contexto de utilização

#include <stdio.h>#include <stdlib.h>main (int argc, char *argv[]){

int i, N = atoi (argv[1]), sw = atoi (argv[2]);int *a = malloc (N * sizeof(int));if (sw)

for (i = 0; i < N; i++)a[i] = 1000 * (1.0 * rand() / RAND_MAX);

elsewhile (scanf(“%d”, &a[N]) == 1) N++;

sort (a, 0, N-1);for (i = 0; i < N; i++) printf(“%3d”, a[i]);printf(“\n”);

}

AED (IST/DEEC) 10

Ordenação por selecção - Selection Sort• Um dos mais simples. Algoritmo:

– procurar menor elemento e trocar com o elemento na 1a posição– procurar 2o menor elemento e trocar com o elemento na 2a posição– proceder assim até ordenação estar completa

void selection (Item a[], int l, int r){int i, j;for (i = l; i < r; i++) {

int min = i;for (j = i+1; j <= r; j++)

if (less(a[j], a[min])) min = j;exch(a[i], a[min])

}}

…

Cicloexterior

Ciclointerior

AED (IST/DEEC) 11

A A E E G I N T O X S M P L R

Selection Sort - Exemplo de AplicaçãoA S O R T I N G E X A M P L E

A A E E T I N G O X S M P L RA A E E G I N T O X S M P L R

A A E E G I L T O X S M P N RA A E E G I L M O X S T P N RA A E E G I L M N X S T P O RA A E E G I L M N O S T P X RA A E E G I L M N O P T S X RA A E E G I L M N O P R S X TA A E E G I L M N O P R S X TA A E E G I L M N O P R S T XA A E E G I L M N O P R S T X

A S O R T I N G E X A M P L EA A O R T I N G E X S M P L EA A E R T I N G O X S M P L E

AED (IST/DEEC) 12

Selection Sort - Análise• Ciclo interno apenas faz comparações

– troca de elementos é feita fora do ciclo interno– cada troca coloca um elemento na sua posição final

• número de trocas é N-1 (porque não N?)– tempo de execução dominado pelo número de comparações!

Propriedade: Selection sort usa aproximadamente N2/2comparações e N trocas

Demonstração: para cada item i de 1 a N-1 há uma troca e N-icomparações (ver sombreados no exemplos)Logo há N-1 trocas e (N-1)+(N-2)+...+2+1=N(N-1)/2 comparações

Factos: desempenho é independente da ordenação inicial dos dados; a única coisa que depende desta ordenação é o número de vezes quemin é actualizado (quadrático no pior caso, N log N em média)

AED (IST/DEEC) 13

• Introdução ao problema da ordenação de dados– Simplicidade do problema facilita a compreensão de conceitos

chave em algoritmos– Problema de grande aplicação

• Definição das regras base e interface de utilização– Macros e operações elementares relevantes

• Definições e propriedades gerais• Ordenação por Selecção – “Select sort”

– Descrição– Exemplo de aplicação– Análise de eficiência

Ordenação – Síntese da Aula O1

AED (IST/DEEC) 14

Ordenação por inserção - Insertion SortIdeia: considerar os elementos um a um e inseri-los no seu lugar

entre os elementos já tratados (mantendo essa ordenação)ex: ordenar cartas de jogar– inserção implica arranjar novo espaço ou seja mover um número elevado

de elementos uma posição para a direita– inserir os elementos um a um começando pelo da 1a posição

#define less(A, B) (key(A) < key(B))#define exch(A, B) {Item t = A; A = B; B = t; }#define compexch(A, B) if (less(B,A)) exch(A, B)void insertion(Item a[], int l, int r){

int i, j;for (i = l+1; i <= r; i++)

for (j = i; j > l; j--)compexch (a[j-1], a[j]);

}

…

AED (IST/DEEC) 15

Insertion Sort - Comentários

• Elementos à esquerda do índice corrente estão ordenados mas não necessariamente na sua posição final– podem ainda ter de ser deslocados para a direita para dar lugar a

elementos menores encontrados posteriormente

• Implementação da ordenação por inserção na pág. anterior é ineficiente– código é simples, claro mas pouco eficiente; pode ser melhorado– ilustra bom raciocínio:

• encontrar solução simples• estudar o seu funcionamento• melhorar desempenho através de pequenas transformações

AED (IST/DEEC) 16

Insertion Sort - Melhorar desempenho

• Demasiadas operações de comparação/troca (compexch)– podemos parar se encontramos uma chave que não é maior que a

do item a ser inserido (tabela está ordenada à esquerda)• podemos sair do ciclo interno se less(a[j-1], a[j]) é verdadeira

– modificação torna o algoritmo adaptativo– aumenta desempenho aproximadamente por um factor de 2

• Passa a haver duas condições para sair do ciclo– mudar para um ciclo while– remover instruções irrelevantes

• compexch não é o melhor processo de mover vários dados uma posição para a direita

AED (IST/DEEC) 17

Insertion Sort - Versão adaptativavoid insertion(Item a[], int l, int r){

int i, j;

for (i = l+1; i <= r; i++) {Item v = a[i];j = i;while (j > l && less(v, a[j-1])) {a[j] = a[j-1]; j--;

}a[j] = v;

}}

AED (IST/DEEC) 18

Insertion Sort - Exemplo de Aplicação

A S O R T I N G E X A M P L EA S O R T I N G E X A M P L EA O S R T I N G E X A M P L EA O R S T I N G E X A M P L EA O R S T I N G E X A M P L EA I O R S T N G E X A M P L EA I N O R S T G E X A M P L EA G I N O R S T E X A M P L EA E G I N O R S T X A M P L EA E G I N O R S T X A M P L EA A E G I N O R S T X M P L EA A E G I M N O P R S T X L EA A E G I M N O P R S T X L EA A E G I L M N O P R S T X E A A E E G I L M N O P R S T XA A E E G I L M N O P R S T X

AED (IST/DEEC) 19

Insertion Sort - Análise

Propriedade: Insertion sort usa aproximadamente N2/4comparações e N2/4 pseudo-trocas (translações ou movimentos) no caso médio e o dobro destes valores no pior caso

Demonstração: Fácil de ver graficamente; elementos abaixo dadiagonal são contabilizados (todos no pior caso)

Para dados aleatórios é expectável que cada elemento seja colocado aproximadamente a meio para trás pelo que apenas metade dos elementos abaixo da diagonal devem ser contabilizados

• Factos: em certos casos Insertion sort pode ter bom desempenho (a ver...)

AED (IST/DEEC) 20

Bubble Sort• Talvez o algoritmo mais utilizado e o que muitas pessoas

aprendem

Ideia: fazer múltiplas passagens pelos dados trocando de cada vez dois elementos adjacentes que estejam fora de ordem, até não haver mais trocas– supostamente muito fácil de implementar– usualmente mais lento que os dois métodos elementares estudados

void bubble(Item a[], int l, int r){int i, j;for (i = l; i < r; i++)

for (j = r; j > i; j--)compexch(a[j-1], a[j]);

}

…

AED (IST/DEEC) 21

Bubble Sort - Comentários [1]

• Movendo da direita para a esquerda no ficheiro de dados– quando o elemento mais pequeno é encontrado na primeira passagem

• é sucessivamente trocado com todos à sua esquerda• acaba por ficar na primeira posição

– na segunda passagem o 2o elemento mais pequeno é colocado na sua posição e por diante

– N passagens pelos dados são suficientes!

• É semelhante ao método de selecção– tem mais trabalho para colocar cada elemento na sua posição final

• todas as trocas sucessivas até chegar à posição certa

AED (IST/DEEC) 22

Bubble Sort - Comentários [2]

• Algoritmo pode ser melhorado, tal como o algoritmo de inserção– código é muito semelhantes mas não igual

• ciclo interno de Insertion Sort percorre a parte esquerda(ordenada) da tabela

• ciclo interno de Bubble Sort percorre a parte direita(não ordenada) da tabela

– no final de cada passagem podemos testar se houve mudanças

AED (IST/DEEC) 23

Bubble Sort - Exemplo de AplicaçãoA S O R T I N G E X A M P L E

A A E S O R T I N G E X L M P A A E E S O R T I N G L X M PA A E E G S O R T I N L M X PA A E E G I S O R T L N M P XA A E E G I L S O R T M N P XA A E E G I L M S O R T N P XA A E E G I L M N S O R T P XA A E E G I L M N O S P R T XA A E E G I L M N O P S R T XA A E E G I L M N O P R S T XA A E E G I L M N O P R S T X

A A E E G I L M N O P R S T XA A E E G I L M N O P R S T X

A A S O R T I N G E X E M P L

A A E E G I L M N O P R S T X

AED (IST/DEEC) 24

Bubble Sort - AnálisePropriedade: Bubble sort usa aproximadamente N2/2

comparações e N2/2 trocas no caso médio e no pior caso

Demonstração: A i-ésima passagem de Bubble Sort requerN-i operações de comparação/troca, logo a demonstração ésemelhante a Selection sort

Factos: Algoritmo pode depender criticamente dos dados se for modificado para terminar quando não houver mais trocas– se o ficheiro estiver ordenado, apenas um passo é necessário– se estiver em ordenação inversa então na i-ésima passagem são

precisas N-1 comparações e trocas– caso médio é semelhante (análise mais complexa)

AED (IST/DEEC) 25

Comparação dos algoritmos elementaresde ordenação [1]

• Tempos de execução quadráticos

Selection Insertion BubbleComparações N2/2 N2/4 N2/2

Trocas N N2/4 ≈ N2/2

AED (IST/DEEC) 26

Comparação dos algoritmos elementaresde ordenação [2]

• Ficheiros com elementos grandes e pequenas chaves– Selection Sort é linear no número de dados

• N dados com tamanho M (palavras/words)– comparação - 1 unidade; troca - M unidades

• N2/2 comparações e NM custo de trocas• termo NM domina• custo proporcional ao tempo necessário para mover os dados

• Ficheiros quase ordenados– Insertion sort e Bubble sort são quase linearesèos melhores algoritmos de ordenação podem ser quadráticos neste

caso!

AED (IST/DEEC) 27

Comparação dos algoritmos elementares de ordenação [3]

AED (IST/DEEC) 28

• Ordenação por inserção – “Insertion sort”– Versão elementar– Versão adaptativa– Exemplo de aplicação– Análise de Eficiência

• “Bubble sort” – Breve referência– Descrição do algoritmo e análise funcionamento– Exemplo de aplicação– Análise de eficiência

• Comparação dos três primeiros algoritmos elementares– Em número de comparações e trocas– Na evolução da tabela durante a execução – exemplo gráfico


AED (IST/DEEC) 29

Shellsort - Melhorar a eficiência [1]

• Insertion sort é lento: apenas envolve trocas entre items adjacentes– se o menor item está no final da tabela, serão precisos N passos para o

colocar na posição correcta

• Shellsort:– acelerar o algoritmo permitindo trocas entre elementos que estão

afastados– como?

AED (IST/DEEC) 30


Ideia: rearranjar os dados de forma a que tenham a propriedadeque olhando para cada h-ésimo elemento estão ordenados– dados dizem-se h-ordenados– é equivalente a h sequências ordenadas entreligadas (entrelaçadas)

• Usando valores de h grandes é possível mover elementos na tabela grandes “distâncias” o que torna mais fácil h-ordenar mais tarde com h pequenos– usando este procedimento para qualquer sequência de h's que termine

em 1 vao produzir um ficheiro ordenado– cada passo torna o próximo mais simples

AED (IST/DEEC) 31


• Outra forma de ver o algoritmo: – a tabela é dividida em partições, cada uma contendo os objectos de

índice % hexemplo: para uma tabela de 15 posições e h=4• índices resto 0, i%4=0, são: 0, 4, 8, 12• índices resto 1, i%4=1, são: 1, 5, 9, 13• índices resto 2, i%4=2, são: 2, 6, 10, 14• índices resto 3, i%4=3, são: 3, 7, 11, 15

è dentro de cada partição é feita uma ordenação por inserção

• Exemplo permite visualizar bem o algoritmo...

AED (IST/DEEC) 32

h-Ordenação - Exemplo: h=4

i%4=00,4,8,12

A S O R T I N G E X A M P L EA S O R E I N G T X A M P L EA S O R E I N G P X A M T L E

i%4=11,5,9,13

A I O R E S N G P X A M T L EA I O R E S N G P X A M T L EA I O R E L N G P S A M T X E

i%4=22,6,10,14

A I N R E L O G P S A M T X EA I A R E L N G P S O M T X EA I A R E L E G P S N M T X O

i%4=33,7,11

A I A G E L E R P S N M T X OA I A G E L E M P S N R T X O

A I A G E L E M P S N R T X O

AED (IST/DEEC) 33

Implementação de Shellsort [1]

• Possível fazer melhor: sub-ficheiros são independentes– quando h-ordenamos os dados inserimos qualquer elemento entre

os do seu (h) sub-ficheiro movendo elementos maiores para a direita

• basta usar insertion code com incrementos/decrementosde h em vez de 1

– implementação de Shellsort usa um passo de Insertion sort pelo ficheiro para cada incremento

• Tabela não fica completamente ordenada depois da 1a

ordenação das várias partições– é necessário repetir com uma série de partições– isto é, não basta escolher/usar um só h!

AED (IST/DEEC) 34

Shellsort - Exemplo de aplicação [1]

Partiçõesestãoentrelaçadas

A S O R T I N G E X A M P L EA I O R T S N G E X A M P L EA I N R T S O G E X A M P L EA I N G T S O R E X A M P L EA I N G E S O R T X A M P L EA I N G E S O R T X A M P L EA I A G E S N R T X O M P L EA I A G E S N M T X O R P L EA I A G E S N M P X O M T L EA I A G E L N M P S O R T X EA I A G E L E M P S N R T X O

AED (IST/DEEC) 35

Implementação de Shellsort [2]Solução óbvia: para cada h usar Insertion Sort

independentemente em cada um dos h sub-ficheiros

int h = 4;for (i = l+h; i <= r; i++) {

Item v = a[i];j = i;while (j-h >= l && less(v, a[j-h])) {

a[j] = a[j-h];j -= h;

}a[j] = v;

}

AED (IST/DEEC) 36

Sequência de Ordenação• Difícil de escolher

– propriedades de muitas sequências foram já estudadas– possível provar que umas melhores que outras

• ex: 1, 4, 13, 40, 121, 364, 1093, 3280, ... (Knuth, 3*hant+1)melhor que1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ... (Shell, 2i )

– Porquê?mas pior (20%) que 1, 8, 23, 77, 281, 1073, 4193, … (4i+1 + 3 2i + 1)

– na prática utilizam-se sequências que decrescem geometricamente para que o número de incrementos seja logarítmico

– a sequência óptima não foi ainda descoberta (se é que existe)– análise do algoritmo é desconhecida

• ninguém encontrou a fórmula que define a complexidade• complexidade depende da sequência

AED (IST/DEEC) 37

Shellsort

void shellsort(Item a[], int l, int r){

int i, j, k;int incs[16] = { 1391376, 463792, 198768, 86961, 33936,

13776, 4592, 1968, 861, 336, 112, 48,21, 7, 3, 1 };

for ( k = 0; k < 16; k++) {int h = incs[k];for (i = l+h; i <= r; i++) {

Item v = a[i];j = i;while (j-h >= l && less(v, a[j-h])) {

a[j] = a[j-h];j -= h;

}a[j] = v;

}}

}

AED (IST/DEEC) 38

Shellsort - Exemplo de aplicação [2]

A S O R T I N G E X A M P L EA S O R T I N G E X A M P L EA E O R T I N G E X A M P L S

A E O R T I N G E X A M P L S

A E N R T I O G E X A M P L SA E N G T I O R E X A M P L SA E N G E I O R T X A M P L SA E N G E I O R T X A M P L SA E A G E I N R T X O M P L SA E A G E I N M T X O R P L SA E A G E I N M P X O R T L SA E A G E I N M P L O R T X SA E A G E I N M P L O R T X S

A E A G E I N M P L O R T X SA A E G E I N M P L O R T X SA A E G E I N M P L O R T X SA A E E G I N M P L O R T X SA A E E G I N M P L O R T X SA A E E G I N M P L O R T X SA A E E G I M N P L O R T X SA A E E G I M N P L O R T X SA A E E G I L M N P O R T X SA A E E G I L M N O P R T X SA A E E G I L M N O P R T X SA A E E G I L M N O P R T X SA A E E G I L M N O P R T X SA A E E G I L M N O P R S T XA A E E G I L M N O P R S T X

A E O R T I N G E X A M P L S

AED (IST/DEEC) 39

Análise de Shellsort• Propriedades:

– o resultado de h-ordenar um ficheiro que está k-ordenado é um ficheiro que está simultaneamente h- e k-ordenado

– Shellsort faz menos do que O(N3/2) comparações para os incrementos 1, 4, 13, 40, 121, 364, 1093, ...

– Shellsort faz menos do que O(N4/3) comparações para os incrementos 1, 8, 23, 77, 281, 1073, 4193, 16577, ...

• Nota: sequências até agora usam incrementos que são primos entre si– Shellsort faz menos do que O(N log2 N) comparações para os

incrementos 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81

• Shellsort é um exemplo de um algoritmo simples cuja análise é complicada:– sequência óptima, e análise completa não são conhecidos!

• Alguém consegue encontrar uma sequência que bata1, 2, 7, 21, 48, 112, 336, ...??

AED (IST/DEEC) 40

Shellsort - Exemplo Gráfico

• Graficamente parece que um elástico, preso nos cantos puxa os pontos para a diagonal

AED (IST/DEEC) 41

Vantagens de Shellsort

• rápido/eficiente• pouco código• melhor método para ficheiros pequenos e médios• aceitável para elevados volumes de dados

èMuito utilizado na prática, embora dificil de compreender!

AED (IST/DEEC) 42

• “Shellsort”– Apresentado como uma variante de aceleração do

“Insertion sort”– Descrição– Implementação

• Sequências de ordenação

– Exemplo de aplicação– Discussão da eficiência do algoritmo

• Condicionada pela sequência de ordenação utilizada

– Exemplo gráfico da evolução da tabela– Vantagens relativamente a outros algoritmos


AED (IST/DEEC) 43

#include <stdlib.h>

main (int argc, char *argv[]){

int N = atoi (argv[1]), sw = atoi (argv[2]);int *a = malloc (N * sizeof(int));if (sw)

randinit(a, N);else

scaninit(a, &N);sort (a, 0, N-1);show (a, 0, N-1);

}

Ordenação de outros tipos de dados [1]• Algoritmos estudados são independentes do tipo de dados

– necessário o interface apropriado e a implementação correspondente

while (scanf(“%d”, &a[N]) == 1) N++;

for (i = 0; i < N; i++)a[i] = 1000 * (1.0*rand()/RAND_MAX);

for (i = 0; i < N; i++)printf(“%3d”, a[i]);

printf(“\n”);

AED (IST/DEEC) 44

#include <stdlib.h>#include “Item.h”#include “Array.h”main (int argc, char *argv[]){

int N = atoi (argv[1]), sw = atoi (argv[2]);Item *a = malloc (N * sizeof(Item));if (sw)

randinit(a, N);else

scaninit(a, &N);sort (a, 0, N-1);show (a, 0, N-1);

}

Ordenação de outros tipos de dados [2]• Algoritmos estudados são independentes do tipo de dados

– necessário o interface apropriado e a implementação correspondente

AED (IST/DEEC) 45

Ordenação de outros tipos de dados [3]• Definição do interface

– o tipo apropriado e as funções para sua manipulaçãotypedef double Item;#define key(A) (A)#define less(A, B) (key(A) < key(B))#define exch(A, B) {Item t = A; A = B; B = t; }#define compexch(A, B) if (less(B,A)) exch(A, B)

Item ITEMrand(void);int ITEMscan(Item *);void ITEMshow(Item);

Interface paratipo Item

Item.h

void randinit (Item [], int);void scaninit (Item [], int *);void show (Item [], int, int);void sort (Item [], int, int);

Interface paratipo tabela de Items

Array.h

AED (IST/DEEC) 46

Ordenação de outros tipos de dados [4]• Implementação do interface

– Implementação das funções que operam sobre os dados#include <stdio.h>#include <stdlib.h>#include “Item.h”

double ITEMrand(void){return 1.0 * rand() / RAND_MAX;

}

int ITEMscan(double *x){return scanf(“%lf”, x);

}

void ITEMshow(double x){printf(“%7.5lf “, x);

}

Implementaçãopara tipo Item

(double)

AED (IST/DEEC) 47

Ordenação de outros tipos de dados [5]• Implementação do interface

– Implementação das funções que operam sobre os dados#include <stdio.h>#include <stdlib.h>#include “Item.h”#include “Array.h”

void randinit(Item a[], int N){int i;for (i = 0; i < N; i++) a[i] = ITEMrand();

}

void scaninit(Item a[], int *N){int i =0;;for (i = 0; i < *N; i++)

if (ITEMscan(&a[i]) == EOF) break;*N = i;

}

void show(Item a[], int l, int r){int i;for (i = l; i <= r; i++) ITEMshow(a[i]);printf(“\n”);

}

Implementaçãopara tipo tabela

de Items

AED (IST/DEEC) 48

Ordenação de outros tipos de dados [6]

• Para qualquer tipo de dados– apenas alterar o interface– reescrever as funções que operam sobre os objectos

• rand• show• exch• etc, etc

– algoritmos e rotinas de ordenação (sorting) não necessitam de qualquer alteração

AED (IST/DEEC) 49

Ordenação por índices [1]

• Suponha-se que os objectos a ordenar são strings (vectoresde caracteres):– funções que operam sobre os dados precisam de ter em conta a

questão da alocação de memória para strings– quem deve ser responsável pela gestão desta memória?– e se os objectos são "grandes"? Comparar e mover os objectos

pode ser dispendioso!• imagine que cada objecto é o nome completo de um aluno (ou que é

toda a sua informação: nome, morada, etc)– mesmo que haja uma boa abstracção para operar sobre os objectos

ainda há a questão do custo

• Porquê movê-los?– porque não alterar apenas referência para a sua posição relativa?

AED (IST/DEEC) 50

Ordenação por índices [2]• Solução 1:

– dados numa tabela data[0], ..., data[N-1]– usar uma segunda tabela, a[.], apenas de índices

• inicializado de forma a que a[i] = i, i = 0, ..., N-1– objectivo é rearranjar a tabela de índices de forma a que a[0]

aponte para o objecto com a menor chave, etc– objectos são apenas acedidos para comparação

• Rotinas de ordenação apenas acedem aos dados através de funções de interface:, less, exch, etc– apenas estas têm de ser reescritas

AED (IST/DEEC) 51

Ordenação por índices - Exemplo• Suponha os seguintes dados: data = [“rui”, “carlos”, “luis”]

usamos uma tabela, de índices a = [ 0, 1, 2 ]

– 1o passo: comparar data[a[1]] com data[a[0]]: “carlos” < “rui”pelo que há troca de a[1] com a[0]: a = [ 1, 0, 2 ]

– 2o passo: comparar data[a[2]] com data[a[1]]: “rui” < “luis”pelo que há troca de a[2] com a[1]: a = [ 1, 2, 0 ]

– 3o passo: comparar data[a[1]] com data[a[0]]: “carlos” < “luis”pelo que não há troca

• Os valores ordenados são portanto data[a[0]], data[a[1]] e data[a[2]]

ou seja “carlos” < “luis” < “rui”

(de forma encapotada usámos uma “espécie” de Insertion sort)

AED (IST/DEEC) 52

Ordenação por ponteiros

• Outra solução é a tabela de índices conter de facto ponteiros para os dados– mais geral pois os ponteiros podem apontar para qualquer lado

• items não precisam de ser membros de uma tabela• nem de ter todos o mesmo tamanho

– depois da ordenação, acesso sequencial à tabela de ponteirosdevolve os elementos ordenados

• um exemplo é a função qsort, do C, que implementa o algoritmo quicksort (estudaremos adiante)

AED (IST/DEEC) 53

Ordenação por ponteiros ou índices

• Não-intrusiva em relação aos dados– pode ser efectuada se os dados forem apenas de leitura

• Possível efectuar ordenação em chaves múltiplasex: listagens de alunos, com nome, número e nota

• Evita o custo de mover/trocar os items– pode ser elevado se estes forem grandes quantidades de

informação– mais eficiente em problemas com dados grandes e chaves

pequenas

• E se for preciso retornar os dados ordenados?– ordenar por índice/ponteiro– fazer permutações in-situ (como?)

AED (IST/DEEC) 54

Ordenação de listas ligadas• Semelhante a ordenação de tabelas

– funções de interface diferentes– necessário trabalhar com ponteiros e não apenas com índices

• Trocas podem não ser possíveis– elementos podem ser acedidos por outras estruturas de dados– trocam-se apenas os ponteiros– inserções são na verdade mais simples

• não é preciso mover elementos para a direita, apenas ajustar dois ponteiros

• Algoritmos básicos– alterações simples

AED (IST/DEEC) 55

Exercício - usar Selection Sort para ordenar uma lista ligada

• Estruturas de Dados:– lista de entrada– lista de saída: dados colocados na sua posição final– ponteiros adicionais

Ideia básica– procurar maior elemento na lista– manter ponteiro para o anterior– retirá-lo da lista de entrada– introduzi-lo no início da lista de saída

è Implemente como exemplo!

AED (IST/DEEC) 56

• Ordenação de outros tipos de dados– Implementações estudadas até aqui assumiam ordenação de

inteiros– Definição da interface apropriada

• Protótipos de funções elementares• Definição dos dados

• Para evitar mover grandes quantidades de dados– Ordenação por índices– Ordenação por ponteiros

• Ordenação em listas ligadas– Referência às alterações a introduzir nos algoritmos analisados

• Ao nível dos dados de entrada• Ao nível da interface


Documents

AED AlgoritmoseEstruturasde Dados LEEC -2005/2006