algoritmo inserção

Prévia do material em texto

Algoritmos II
Algoritmos de Ordenação
Vamos ver...
• Métodos de Ordenação ou Classificação
 Troca: Bubble Sort
 Seleção: Selection Sort
 Inserção: Insertion Sort
Conceitos Básicos
 Em vários momentos nos deparamos com a necessidade de consultar dados
ordenados
• Por isso, uma das atividades mais utilizadas na área de TI é a ordenação
 O conceito de um conjunto ordenado de elementos tem importância tanto na
informática como em nossa vida cotidiana
• Exemplo: Imagine quão complicado seria localizar um número de telefone
num catálogo se o mesmo não fosse classificado por ordem alfabética nem
por endereço
Conceitos Básicos
 Ordenar corresponde ao processo de rearranjar um conjunto de objetos em
ordem ascendente ou descendente
 O objetivo principal da ordenação é armazenar dados de forma adequada, de
modo a facilitar a busca na recuperação posterior de itens do conjunto ordenado,
tornando mais ágil a recuperação das informações
Conceitos Básicos
Métodos de ordenação mais utilizados:
1. Insertion Sort (ordenação por inserção) 
2. Buble Sort (Ordenação por bolha) 
3. Select Sort (Ordenação por seleção) 
4. Shell Sort (Ordenação por shell) 
5. Quick Sort (Ordenação rápida) 
6. Heap Sort (Ordenação por pilha) 
7. Merge Sort (Ordenação por intercalação) 
Bubble Sort
Bubble Sort
 Também conhecido como ordenação por bolha ou método da troca.
 É um dos algoritmos de ordenação mais simples e conhecidos que existem.
Bubble Sort
Funcionamento
• Compara pares de valores adjacentes e os troca de lugar se estiverem na ordem 
errada. 
• Trabalha de forma a movimentar, uma posição por vez, o maior valor existente na 
porção não ordenada de um array para a sua respectiva posição no array 
ordenado. 
• Esse processo se repete até que mais nenhuma troca seja necessária, ou seja, os 
elementos já estão ordenados. 
Bubble Sort
Passo a passo 
Bubble Sort
Bubble Sort
 Processo continua até todo o array estar ordenado 
Selection Sort
Selection Sort
 Também conhecido como ordenação por seleção.
 É outro algoritmo de ordenação bastante simples. 
 A cada passo ele seleciona o melhor elemento para ocupar aquela posição do 
array.
 Na prática, possui um desempenho quase sempre superior quando comparado 
com o bubble sort.
Selection Sort
Funcionamento
• A cada passo, procura o menor valor do array e o coloca na primeira posição do 
array.
• Divide o array em duas partes: a parte ordenada, a esquerda do elemento 
analisado, e a parte que ainda não foi ordenada, a direita do elemento. 
• Descarta-se a primeira posição do array e repete-se o processo para a segunda 
posição. 
• Isso é feito para todas as posições do array. 
Selection Sort
Selection Sort
Passo a passo 
 Para cada posição i, procura no restante do array o menor valor para ocupá-la 
Selection Sort
Insertion Sort
Insertion Sort
 Também conhecido como ordenação por inserção.
 Similar a ordenação de cartas de baralho com as mãos. 
 Pegue uma carta de cada vez e a insira em seu devido lugar, sempre deixando as 
cartas da mão em ordem. 
Insertion Sort
 É um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno 
número de elementos. 
 Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita 
e à medida que avança vai deixando os elementos mais à esquerda ordenados.
Insertion Sort
Funcionamento
 O algoritmo percorre o array e para cada posição X verifica se o seu valor está na 
posição correta. 
 Isso é feito andando para o começo do array a partir da posição X e 
movimentando uma posição para frente os valores que são maiores do que o 
valor da posição X.
 Desse modo, teremos uma posição livre para inserir o valor da posição X em seu 
devido lugar. 
Insertion Sort
Insertion Sort
Passo a passo 
 Para cada posição i, movimenta os valores maiores uma posição para frente no 
array 
Insertion Sort