Please enable JavaScript.
Coggle requires JavaScript to display documents.
Unidade III (Bubblesort
Unidade III (Bons
Simples implementação
…
Unidade III
Bubblesort
Unidade III
Bons
- Simples implementação
- Algaritimo pequeno
Contra
- Consome muito recurso computacional
- Mesmo um vetor organizado, ele vai percorrer todo vetor
- Executa n ao quadrado indiferente da organização
O que faz
- Compara to dos os valores da sequência (j) com a primeira posição (i) e troca se for menor que o anterior.
-
Insertion Sort
- Ordenação de cartas
Unidade III - Aula 12
Bons
- A eficiente depende
- melhor caso - vetor quase ordenado = n
- Pior caso - vetor ordenado inversamente
-
O que faz
- Semelhante ao Bubb e Selection dois laços, porém retrocedendo
- Com uma variável temporária (chave) ele armazena o menor e movimenta a anterior, deslocando tudo da esquerda para abrir um espaço para o próximo até j ser menor que 0.
- Na pratica é igual organizar carta de baralho.
Shellsor
- Otimização do Insertion Sort
Bons
- Maior proveito do Insertion Sort
-
O que faz
- Ordena de K em K usando GAP que é um indice de controle. Aproxima os elementos.
- Valores de GAP
- é praticamente o Insertion Sort inserindo o Shellsort (GAP)
- Os GAP faz 3, 2, 1 (aplicando o insertion sort para cada sequencia dessas)
- Após quase organizar ele aplica o Insertion sort
Resumo
- Ordenação por flutuação (Bubblesort)
- Ordenação por seleção (Selectionsort)
- Ordenação por inserção (insertionsort)
- Aproximar elementos, deixando vetores quase ordenados (Shellsort).
Unidade V
Buscas
Busca binária
Aula 20
Como:
- Ela checa o elemento do meio
- Dividir para conquistar
- Ele divide no meio, e segue para o lado que está o valor procurado.
- Aumenta o tempo de busca.
Contra
- Não implementar em arvore de busca binária
-
-
Busca Interpolação
-
Como:
- Ele encontra o meio pelo índice se aproximando do valor chave a ser buscado.
- Reduz a iteração.
- É muito parecido com a busca binária.
-
Busca sequencial
Aula 18
-
Como faz:
- Verifica todos elementos, se encontra retorna a posição.
- Laço simples de repetição.
Contra e bons
- Muito recurso computacional
- Simples implementação
-
Tabelas Hash
Aula 20
Função Hash, que transforma a chave em índice através de dispersão.
- Cria uma tabela auxiliar para organizar os vetores.
- Existem várias fórmulas da função hash.
-
Unidade IV
Ordenação
Mergesort
Aula 14
Bons
- Estável
- Custo computacional reduzido
Contra
- Algoritmo complexo
- Ele utiliza memória auxiliar a cada divisão
O que é:
- Baseado no conceito dividir para conquistar;
- imprementação inerentemente recursiva;
- Após dividir o arranjo partes menores diminuindo o problema.
Como:
- Divide até fica 1 elemento por arranjo
- Depois recursivamente ele vai montando
- dois, quatro, depois oito, etc. organizando em um laço de comparação com variável x(Esquerda) y(direita), k(organizado parcial).
Quicksort
- Classificação por troca de partição
Aula 15
Bons
- Ordena arranjo menores, para ordenar o arranjo todo
- Código levemente complexo.
- Não oucupa memória auxiliar
- É muito rápido.
Contra
- Algoritmo Instável
- Pior caso: Vetores ordenado ou parcialmente.
O que é
- Implementação inerentemente recursiva
- Chama a si mesmo para dividir e conquistar.
Como
- Usa Pivô na posição central.
- Partition faz a partição e encontra o meio
- Faz duas chamadas recursivas.
- Faz uma comparação do pivô com todas as posições.
Heap Sort
Aula 16
Bons
- Faz inserção e remoção em tempo logarítmico.
- Muito eficiente.
-
O que é
- Transforma vertores em arvore binária.
- Ela é uma arvore completa até pelo menos o penúltimo nível
- No último nível deve ser a esquerda quanto for possível.
- São dois tipos de heap: Max-heap (nó pai é sempre é maior ou igual aos seus filhos.
Min-heap:
-