Upload
leinylson-fontinele
View
44
Download
0
Embed Size (px)
Citation preview
# Pesquisa e Ordenação #Aula 04 – Métodos de Ordenação
(Inserção – Insertion Sort)
Prof. Leinylson Fontinele Pereira
Na aula anterior...
Métodos de ordenação
Troca# Bubble Sort
17:28 Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
O que vamos aprender?
Métodos de ordenação
Inserção# Inserction Sort
17:28 Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Vamos começar?
17:28 4 Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
17:28 5
Ordenação comInsertionSort
Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação
Ordenação com InsertionSort
17:28
Este método, considera-se a matriz a ordenar como uma matrizdividida em duas sub-matrizes (esquerda e direita), com a da esquerdaordenada e o da direita desordenada.
Os elementos são retirados um de cada vez da sub-matriz da esquerda(não ordenada), e move-se esse elemento para o sub-matriz daesquerda, inserindo-o na posição correta para manter a sub-matriz daesquerda ordenada, terminando o processo quando a sub-matriz dadireita ficar vazia.
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Em cada passo, a partir do 𝑖 = 2, oI-ésimo elemento da sequência fonteé apanhado e transferido para asequência destino, sendo inserido noseu lugar apropriado.
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pior caso = 𝑂(𝑛²)
Melhor caso = 𝑂(𝑛)Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Visualizar Execução
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Ordenação com InsertionSort
17:28
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
O número mínimo de comparações e movimentos ocorre quando os itens estãooriginalmente em ordem.
O número máximo ocorre quando os itens estão originalmente na ordem reversa.
É o método a ser utilizado quando o arquivo está “quase” ordenado.
É um bom método quando se deseja adicionar uns poucos itens a um arquivoordenado, pois o custo é linear.
O algoritmo de ordenação por inserção é estável.
Concluindo...
17:28 29 Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Nesta aula aprendemos...
17:28
Métodos de ordenação
Inserção# Inserction Sort
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Na próxima aula veremos...
17:28 Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)
Métodos de ordenação
Distribuição# Ordenação digital
# Radix Sort
# Bucket Sort
Material: https://sites.google.com/site/leinylsonnassau
17:28
Material baseado nas aulas de:
Linguagem C Descomplicada , Dr. André R. Backes.
Desenvolvimento de atividades lúdicas p/ o ensino-aprendizagemda disciplina Complexidade de Algoritmos, Giselle Lima.
Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)