Tema 5 - mod 1

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

TEMA 5 - ORDENAÇÃO
MOD 1 - MÉTRICAS DE CLASSIFICAÇÃO E ESCOLHER O MÉTODO ADEQUADO PARA RESOLVER PROBLEMAS
___ORDENAÇÃO
Pode-se dizer que um algoritmo de ordenação é a entidade que recebe como entrada uma instância do problema de ordenação e fornece como saída uma permutação desta entrada, satisfazendo a relação de ordem definida no enunciado do problema.
____Classificação dos algoritmos de ordenação
Os algoritmos de ordenação podem ser classificados segundo diversos parâmetros:
· Complexidade computacional.
· Complexidade de espaço.
· Ordenação interna ou externa.
· Caráter recursivo.
· Estabilidade.
-> COMPLEXIDADE COMPUTACIONAL
Determinar a complexidade de um algoritmo é encontrar uma função matemática.
: N → R, tal que k f(n), onde k > 0 ∈ R e n ∈ N é o tamanho da instância.
A função f é cota assintótica superior para o número de operações elementares necessárias para um algoritmo A resolver todas as instâncias de tamanho n. 
A cota assintótica descrita acima define a notação O, isto é, diz-se que g é O(f) se existe um n0 ∈ N e um k > 0 ∈ R, tal que para todo n > n0, k * f(n) > g(n).
A introdução da notação O permite que a análise de complexidade computacional classifique os algoritmos em classes que determinam seu desempenho. Os algoritmos mais eficientes são aqueles que executam em um tempo proporcional a uma constante e, a partir daí, temos o aumento do tempo de execução.
Busca Linear vs. Busca Binária:
Em uma busca linear, cada elemento de um vetor é verificado sequencialmente, resultando em complexidade O(n). A busca binária, porém, divide o vetor ordenado ao meio a cada passo, com complexidade O(log n), sendo assim mais eficiente em grandes conjuntos de dados. Exemplo: em um vetor de 106 elementos, a busca linear requer 106 comparações, enquanto a busca binária precisa de cerca de 20.
Limite Inferior dos Algoritmos de Ordenação:
Algoritmos de ordenação baseados em comparações têm complexidade mínima O(n log n). Isso se deve ao fato de que cada comparação representa uma decisão sobre a posição de elementos. Esse limite é demonstrado usando uma árvore de decisão, onde cada comparação é um nó interno e cada permutação possível do vetor é uma folha da árvore.
Árvore de Decisão na Ordenação:
A árvore de decisão modela a ordenação como um processo de escolha. Cada nó compara dois elementos, e a altura da árvore determina o número mínimo de comparações. A árvore é binária e completa, com altura proporcional a n log n, que define o limite mínimo de complexidade para algoritmos de ordenação por comparação.
-> COMPLEXIDADE DE ESPAÇO
A complexidade de espaço mede a quantidade de memória que um algoritmo requer para sua execução. Geralmente, usa-se O(n) espaço para armazenar dados, mas é possível otimizar a complexidade de tempo em troca de mais memória.
No exemplo de ordenação de inteiros entre 0 e 100000, cria-se um vetor auxiliar AUX de tamanho 100000, marcando as posições conforme os valores aparecem em V . Após isso, o vetor V é preenchido com os índices marcados, resultando em uma ordenação com complexidade de tempo O(n), mas com um custo de memória elevado devido ao tamanho do universo de valores. 
1	Para i = 1 até n
2		aux [V[i]]=1;
________________________________________________________________
1	j=0;
2	para i = 0 ate 100000
3		se (aux[i] == 1)
4			inicio
5				V[j]=i;
5				j++;
7			fim
Essa técnica é pseudolinear, pois o espaço usado depende do conjunto universo e não do tamanho da entrada, resultando em maior consumo de memória.
-> ORDENAÇÃO INTERNA X EXTERNA
Esta característica refere-se ao local onde os dados estão armazenados. Memória principal (RAM) e memória secundária (disco ou SSD) diferem em acesso e velocidade. A memória principal permite acesso aleatório byte a byte e é muito mais rápida, com tempo de acesso em nanosegundos. A memória secundária é acessada em blocos, com tempo de acesso em milissegundos.
Algoritmos de ordenação interna operam com todos os dados na memória principal, enquanto algoritmos de ordenação externa conseguem ordenar dados na memória secundária, mas ainda dependem de copiar partes para a memória principal, onde o processamento ocorre, seguindo o modelo de von Neumann.
-> CARÁTER RECURSIVO
Algoritmos de ordenação podem ser recursivos ou sequenciais. O Merge Sort é um exemplo recursivo que usa a estratégia "dividir para conquistar": ele divide o vetor ao meio até que cada elemento esteja isolado, depois concatena esses elementos em ordem para formar o vetor final ordenado. Esse processo de concatenação seleciona o menor elemento entre dois vetores e os organiza em sequência.
A complexidade do Merge Sort é O(n log ⁡n), pois realiza log n divisões e, em cada nível, percorre n elementos.
-> ESTABILIDADE
Um algoritmo de ordenação é estável se mantém a ordem dos elementos que já estão corretamente posicionados, evitando trocas desnecessárias em sequências ordenadas. Isso pode reduzir o número de operações em alguns casos, mas não afeta a complexidade teórica do algoritmo.
____ALGORITMOS NÃO BASEADOS EM COMPARAÇÃO ENTRE ELEMENTOS DO VETOR
A maioria dos algoritmos de ordenação baseia-se em comparações entre elementos, mas há algoritmos que ordenam sem comparar diretamente, o que permite complexidade menor que O(n log⁡ n). Um exemplo é o bucket sort, que organiza inteiros em "baldes" com base em dígitos de maior para menor ordem. Cada iteração separa os números conforme o dígito atual e, ao final, os baldes são concatenados para formar a sequência ordenada.
MOD 2 - Distinguir os algoritmos de ordenação por bolha, inserção e seleção para soluções rápidas e eficientes.
image.png