Sr. Araújo

AED
Algoritmos 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 ambosAED (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