AULA_4_Selecao_Insercao

Prévia do material em texto

Aula 4 
Algoritmo e Estrutura de Dados II 
COM-112 
Vanessa Souza 
Universidade Federal de Itajubá – Instituto de Matemática e Computação 
Classificação dos Métodos de Ordenação 
Ordenação 
Interna 
BubleSort 
Seleção 
Inserção 
MergeSort 
Quicksort 
Externa Intercalação 
Bolha 
comparação 
movimentação 
Bolha 
comparação 
movimentação 
Calcular a complexidade 
assintótica do bolha 
Bolha 
Bolha 
Esse bolha pode ficar 
mais inteligente... 
Bolha 
Bolha 
Bolha 
Calcular a complexidade 
assintótica do bolha 
inteligente 
Bolha 
Calcular a complexidade 
assintótica do bolha 
inteligente 
)( 2n
Bolha 
 Uma das principais vantagens do algoritmo 
BubbleSort é sua simplicidade. 
 
 O algoritmo tem complexidade assintótica O(n2) e 
funciona muito bem em vetores quase ordenados. 
 
 BubbleSort x BubbleSortInteligente 
Classificação dos Métodos de Ordenação 
Ordenação 
Interna 
BubleSort 
Seleção 
Inserção 
MergeSort 
Quicksort 
Externa Intercalação 
Ordenação por Seleção 
 Ideia 
 Este algoritmo usa um marcador para dividir as partes 
ordenada (à esquerda) e desordenada (à direita) do vetor. 
 Procura-se na parte desordenada pelo menor elemento e 
troca-se esse elemento com o elemento sob o marcador. 
 Em seguida, avança-se o marcador. O processo se repete até 
que exista apenas um elemento a partir do marcador. 
Ordenação por Seleção 
5 3 1 2 4 
Desordenado Ordenado 
Ordenação por Seleção 
5 3 1 2 4 
Desordenado Ordenado 
Procura pelo menor elemento 
Ordenação por Seleção 
1 3 5 2 4 
Desordenado Ordenado 
Troca com a posição do marcador 
Ordenação por Seleção 
1 3 5 2 4 
Desordenado Ordenado 
Anda com o marcador 
Ordenação por Seleção 
1 3 5 2 4 
Desordenado Ordenado 
Repete o processo 
Ordenação por Seleção 
1 2 5 3 4 
Desordenado Ordenado 
Repete o processo 
Ordenação por Seleção 
1 2 5 3 4 
Desordenado Ordenado 
Repete o processo 
Ordenação por Seleção 
1 2 5 3 4 
Desordenado Ordenado 
Repete o processo 
Ordenação por Seleção 
1 2 3 5 4 
Desordenado Ordenado 
Repete o processo 
Ordenação por Seleção 
1 2 3 5 4 
Desordenado Ordenado 
Repete o processo 
Ordenação por Seleção 
1 2 3 5 4 
Desordenado Ordenado 
Repete o processo 
Ordenação por Seleção 
1 2 3 4 5 
Desordenado Ordenado 
Repete o processo 
Ordenação por Seleção 
1 2 3 4 5 
Ordenado 
Ordenação por Seleção 
 Exercício 
 Ordenar por seleção o seguinte vetor 
5 4 3 2 1 
Desordenado Ordenado 
Ordenação por Seleção 
 Exercício 
 Ordenar por seleção o seguinte vetor 
1 2 3 4 5 
Desordenado Ordenado 
Ordenação por Seleção 
 Vamos programar?? 
 
 Ordenar por Seleção 
 
 Encontrar o Menor 
Ordenação por Seleção 
Ordenação por Seleção 
Menor é a posição do vetor que contém o menor elemento 
Ordenação por Seleção 
)( 2n
Ordenação por Seleção 
Uma prática 
comum é 
implementar uma 
função troca 
Classificação dos Métodos de Ordenação 
Ordenação 
Interna 
BubleSort 
Seleção 
Inserção 
MergeSort 
Quicksort 
Externa Intercalação 
Ordenação por Inserção 
InsertionSort 
 Ideia: Também usa marcador mas, inicialmente, 
marcador = 1. Seja x o primeiro elemento da parte 
desordenada. Troca-se x de posição com os 
elementos que aparecem à esquerda até que x esteja 
em sua posição correta, e avança-se o marcador. 
 O processo se repete até que a parte desordenada do vetor 
esteja vazia. 
 Insere vet[marcador] na posição correta da parte ordenada 
do vetor 
InsertionSort 
5 3 1 2 4 
Desordenado Ordenado 
Procura na parte ordenada do vetor, o local correto de 3 
InsertionSort 
5 3 1 2 4 
Desordenado Ordenado 
Procura na parte ordenada do vetor, o local correto de 3 
InsertionSort 
3 5 1 2 4 
Desordenado Ordenado 
Insere o 3 no lugar do 5 
Anda com o marcador 
InsertionSort 
3 5 1 2 4 
Desordenado Ordenado 
Procura na parte ordenada do vetor, o local correto de 1 
InsertionSort 
3 5 1 2 4 
Desordenado Ordenado 
Local correto de 1 : posição 0 
InsertionSort 
1 3 5 2 4 
Desordenado Ordenado 
Insere o 1 no seu local correto, movimentando as demais posições 
InsertionSort 
1 3 5 2 4 
Desordenado Ordenado 
Repete o processo 
InsertionSort 
1 3 5 2 4 
Desordenado Ordenado 
Repete o processo 
InsertionSort 
1 2 3 5 4 
Desordenado Ordenado 
Repete o processo 
InsertionSort 
1 2 3 5 4 
Desordenado Ordenado 
Repete o processo 
InsertionSort 
1 2 3 5 4 
Desordenado Ordenado 
Repete o processo 
InsertionSort 
1 2 3 4 5 
Desordenado Ordenado 
Repete o processo 
InsertionSort 
1 2 3 4 5 
Ordenado 
Vetor ordenado 
InsertionSort 
 Na implementação... 
1 3 5 2 4 
Desordenado Ordenado 
2 
InsertionSort 
 Na implementação... 
1 3 5 5 4 
Desordenado Ordenado 
2 
InsertionSort 
 Na implementação... 
1 3 3 5 4 
Desordenado Ordenado 
2 
InsertionSort 
 Na implementação... 
1 3 3 5 4 
Desordenado Ordenado 
2 
InsertionSort 
 Na implementação... 
1 2 3 5 4 
Desordenado Ordenado 
2 
InsertionSort 
 Vamos programar? 
InsertionSort 
)( 2n
Exercício 
 Em dupla, demonstre passo a passo a ordenação do 
vetor X pelos métodos da Bolha Inteligente, Seleção e 
da Inserção. 
 Indique o número de comparações e movimentações 
efetuadas. 
X = [6, 21, 17, 32, 14] 
 
 Tempo : 15 minutos 
 
Comparação entre os métodos 
 Os algoritmos vistos até agora são muito citados por 
sua simplicidade. 
 
 Todos possuem complexidade assintótica do pior 
caso de O(n2). 
 
 Costumam ser bons para arquivos pequenos e já 
quase ordenados. 
Comparação entre os métodos 
 Existe uma outra gama de algoritmos de ordenação 
mais eficientes (O(log2n)). 
 mergeSort 
 quickSort 
 
 Esses algoritmos baseiam-se na estratégia de DIVIDIR 
PARA CONQUISTAR 
 
 Implementações mais difíceis – estritamente 
recursivos 
Para Casa 
 
 Estudar e implementar o algoritmo de Seleção