Pesquisa e Ordenação - Aula 04 - Métodos de Ordenação (Inserção - Insertion sort)

# 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?


Inserção# Inserction Sort


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)


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.



17:28

Pior caso = 𝑂(𝑛²)

Melhor caso = 𝑂(𝑛)Pesquisa e Ordenação: Aula 04 – Métodos de Ordenação (Inserção)


17:28



17:28



17:28



17:28



17:28



17:28



17:28



17:28



17:28



17:28



17:28



17:28



17:28



17:28



17:28



17:28



17:28



17:28



17:28

Visualizar Execução


aula atual/Exploring Sorting Algorithms.html


17:28


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


Inserção# Inserction Sort


Na próxima aula veremos...



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.


Alguma Dúvida?

17:28

Até a próxima aula...

[email protected]

Education

Pesquisa e Ordenação - Aula 04 - Métodos de Ordenação (Inserção - Insertion sort)