Please enable JavaScript.
Coggle requires JavaScript to display documents.
IF672 (2020.1) - Levitin Aluno: Marcos André - Coggle Diagram
IF672 (2020.1) - Levitin Aluno: Marcos André
(3.1) Selection Sort e Bubble Sort Cap. 3 (98–102)
Aplicações de força bruta
Rearranjar os termos em ordem não decrescente
Forma direta de resolver problemas de ordenação
Selection Sort
Trocar o menor elemento com o primeiro
Achar o menor entre os n - 1 elementos e trocar com o segundo
Depois de n - 1 passos, a lista está ordenada
Tamanho da Entrada: Número de elementos n
Operação básica: comparação de chaves
C(n) = ((n-1)*n)/2
θ(n²) para todas as entradas
Número de trocas é θ(n)
Diferença positiva para outros algoritmos
Bubble Sort
Compara elementos adjacentes e faz a troca se tiverem fora de ordem
"Bubbling up" maior elemento pra última posição na lista
Após n -1 passos a lista está ordenada
Comparações de chave são sempre as mesmas
θ(n²)
O número de trocas de chave depende da entrada
Pior caso: ((n-1)n)/2 que pertence a θ(n²)
Se uma passagem não faz trocas, pode ser parado
Não é muito eficiente
A primeira aplicação de um algoritmo de força bruta geralmente pode ser melhorada
(4) Decrease-and-Conquer (131–136)
Relação entre uma solução para uma dada instância
Solução para sua instância menor
Relação estabelecida
Top down
Principalmente recursiva
Bottom up
Iterativa
solução para a menor instância do problema
Abordagem Incremental ("Incremental approach")
Decrease by a constant
Tamanho da instância é reduzido pela mesma constante a cada iteração
Geralmente a constante é 1
Decrease by a constant factor
Reduzir a instância pelo mesmo fator constante a cada iteração
Geralmente o fator é 2
Muito eficientes
Variable size decrease
O padrão de redução de tamanho varia de uma iteração para outra
Algoritmo de Euclides
(4.1) Insertion Sort
Decrease-by-one ordenando um Array
Problema menor: Ordenar um subarray
A partir disso inserir o que falta da lista
Ideia recursiva, mas é mais eficiente iterativamente
Operação básica: Comparação de chaves
Depende da entrada
Pior caso: array de elementos decrescentes
((n-1)n)/2 que pertence a θ(n²)
Melhor caso: Ordenado em ordem não decrescente
n-1 pertence a θ(n)
Arquivos quase ordenados
Performance excelente
Médio caso: Arrays randomicamente ordenadas
n²/4 pertence a θ(n²)
Tem o maior destaque entre os algoritmos de ordenação
"shellsort"
(5) Divide-and-Conquer (169-175)
Plano Geral
Problema dividido em subproblemas
Subproblemas resolvidos
Soluções para os subproblemas são combinados para ter uma solução pro problema original
Nem sempre é mais eficiente que o força bruta
Tempo gasto executando o plano é menor que para outros métodos
Algoritmos mais importantes e eficientes
Computações paralelas
Geralmente é usado a divisão em duas instâncias
Recorrência geral do Divide-and-Conquer
T(n) = aT(n/b) + f(n)
Teorema da eficiência depende da fórmula
Calcula a ordem de crescimento sem resolver a recorrência
Resposta não é exata
(5.1) Mergesort
Divide um array em duas metades
Ordena cada um recursivamente
Junta os dois arrays menores em um único ordenado
Como pode ser feito
Dois ponteiros (Indices do array) para os primeiros elementos dos arrays juntados
São comparados e o menor é adicionado para uma nova array construída
Index do menor elemento incrementado
Operação é repetida até a exaustão
Elementos que restam do outro array são copiados para o fim do novo array
Eficiência
Pior caso: Cworst(n) pertence a θ(n log n)
Mínimo teórico
Médio caso: 0.25n menor que o pior caso
Estabilidade diferencial
Falha
Quantidade linear de armazenamento extra
Algoritmo resultante é complicado e apenas de interesse teórico
Variações
Bottom up
Juntando pares dos elementos do array
Juntando os pares ordenados e por aí vai
Evita o uso de pilha
Multiway mergesort
Dividir uma lista para ser ordenada em mais de duas partes
Ordenar cada recursivamente
Juntar elas
Útil para ordenar arquivos em dispositivos de memória secundários