Algoritmos e Estruturas de Dados [LEEC] (2024/2025)
Aulas teóricas
Artur Miguel Dias
Teórica 09 (16/mai/2025)
A importância da ordenação no software.
Dicionário ordenado implementado usando pesquisa dicotómica e inserção ordenada.
O algoritmo "ordenação por seleção" (selection sort).
Slides
Ordenação
Usamos ordenação:
- para produzir listagem ordenadas (geralmente, através de iteradores ordenados);
- para manter os dados ordenados e assim acelerar imenso a operação de pesquisa.
DicionarioVetorOrd.c
Implementação do dicionário usando um vetor que mantemos permanentemente ordenado.
(O ficheiro "DicionarioVetorOrd.h" não muda.)
Os pontos importantes:
- A função auxiliar posDicionario faz pesquisa dicotómica. Tem complexidade logarítmica. Portanto é muito mais eficiente do que na versão baseada em vetor não ordenado.
- As funções existeDicionario e elementoDicionario recolhem os benefícios da nova função posDicionario e também ficam com complexidade logarítmica e muito eficientes.
- A função acrescentaDicionario fica menos eficiente porque tem de procurar a posição de inserção e depois empurrar vários valores para a frente. A versão baseada em vetor não ordenado colocava simplesmente o novo objeto no final.
- A função removeDicionario continua a ter de puxar vários valores para trás e portanto não melhora nem piora.
Conclusão é melhor usar a implementação "DicionarioVetorOrd.c", em vez de "DicionarioVetor.c", se existirem muitas pesquisas no dicionário, mas poucas inserções.
Algoritmo de ordenação por seleção (Vetor.c)
A função ordenaVetor ordena um vetor usando o algoritmo "ordenação por seleção".
Este algoritmo tem complexidade quadrática, ou seja é pouco eficiente. Mas tem a vantagem de ser bastante simples e é o único que estudamos em AED.
A ordenação deve ser feita raramente, porque mesmo os melhores algoritmos não são tão eficientes como desejaríamos.
Note que no dicionário ordenado não usámos o algoritmo de ordenação. Usámos, sim, inserção ordenada.
#24
