2014826_155251_alex-ed1-semana5-1-ordenacao

Prévia do material em texto

Estrutura de Estrutura de 
Dados IDados IDados IDados I
Prof. Alex Salgado
Curso: Sistemas de Informação
8/26/2014 1
AgendaAgenda
• Algoritmos de ordernação
• Algoritmos de pesquisa
2
AvisosAvisos
• AV1: 18/09/2014
3
Bibliografia recomendadaBibliografia recomendada
Básica:
• SZWARCFITER, J. L; Markenzon, L. Estruturas de dados e seus algoritmos. Rio de 
Janeiro: LTC Editora, 1994.
• TENENBAUM, A. M; Langsam, Y; Augenstein, M. J. Estruturas de Dados usando C.
São Paulo: Makron Books, 2004.
• VELOSO, P. Estruturas de Dados. Rio de Janeiro: Campus, 1983.
•
Complementar:
• CORMEN,T.H. Algoritmos: teoria e prática. Elsevier, 2002.
• KERNIGHAN, B.W; RITCHIE, D.M. C A linguagem de programação padrão • KERNIGHAN, B.W; RITCHIE, D.M. C A linguagem de programação padrão 
ANSI. Campus, 1999.
• MIZRAHI, V. V. Treinamento em Linguagem C: Módulo 1. São Paulo: Makron Books, 
1990.
• MIZRAHI, V. V. Treinamento em Linguagem C: Módulo 2. São Paulo: Makron Books, 
1990.
• MANBER, U. Introduction to algorithms: A creative approach . Addison-Wesley, 
1989.
Outras Fontes
• Waldemar Celes, Renato Cerqueira, José Lucas Rangel, Introdução a Estruturas de 
Dados, Editora Campus (2004)
8/26/2014Footer Text 4
Algoritmos de OrdenaçãoAlgoritmos de Ordenação
E se os números não estiverem ordenados ?
Quanto tempo vai demorar para ordená-los, antes de 
pesquisar ?
5
Algoritmos de Ordenação Algoritmos de Ordenação –– BubbleBubble SortSort
Bubblesort – método de bolha
O bubble sort, ou ordenação por 
flutuação (literalmente "por 
bolha"), é um algoritmo de 
ordenação dos mais simples. A 
idéia é percorrer o vetor diversas 
vezes, a cada passagem 
fazendo flutuar para o topo o 
maior elemento da sequência. 
6
maior elemento da sequência. 
Essa movimentação lembra a 
forma como as bolhas em 
um tanque de água procuram 
seu próprio nível, e disso vem o 
nome do algoritmo.
Algoritmos de Ordenação Algoritmos de Ordenação –– BubbleBubble SortSort
Algoritmos de Ordenação Algoritmos de Ordenação –– BubbleBubble SortSort
Exercício 3 Exercício 3 –– BubbleBubble SortSort
Com base nos ensinamentos, tente implementar 
uma função que ordene um vetor de tamanho 
conhecido utilizando o algoritmo de bolha.
Algoritmos de Ordenação Algoritmos de Ordenação –– BubbleBubble SortSort
Exercício 4 Exercício 4 –– BubbleBubble SortSort
Considere agora que o vetor está ordenado. O que 
poderia melhorar no seu algoritmo ?
Algoritmos de Ordenação Algoritmos de Ordenação –– BubbleBubble SortSort
Algoritmos de Ordenação Algoritmos de Ordenação –– BubbleBubble SortSort
Algoritmos de Ordenação Algoritmos de Ordenação ––
SelectionSelection SortSort
• Definição
• Consiste em encontrar a menor chave por pesquisa 
sequencial. Encontrando a menor chave, essa é 
permutada com a que ocupa a posição inicial do 
vetor, que fica então reduzido a um elemento.
14
vetor, que fica então reduzido a um elemento.
O processo é repetido para o restante do vetor, 
sucessivamente, até que todas as chaves tenham 
sido selecionadas e colocadas em suas posições 
definitivas.
Algoritmos de Ordenação Algoritmos de Ordenação ––
SelectionSelection SortSort
• Definição
• Analogamente as cartas de baralho, espalhe as 
cartas sobre a mesa, selecione a carta de menor 
valor, retire-a do baralho e segure-a na sua mão. 
15
• Esse processo continua até que todas as cartas 
estejam em sua mão. As cartas em sua mão 
estarão ordenadas quando o processo terminar.
Algoritmos de Ordenação Algoritmos de Ordenação –– SelectionSelection SortSort
Sequência:
5 - 3 - 1 - 4 - 2
Verifica quem é o menor e troca com a primeira posição.
1 - 3 - 5 - 4 - 2
Verifica o mesmo só que a partir da segunda posição:
16
Verifica o mesmo só que a partir da segunda posição:
1 - 2 - 5 - 4 - 3
e assim sucessivamente até que não exista mais menores após 
determinada posição:
1 - 2 - 3 - 4 - 5
Algoritmos de Ordenação Algoritmos de Ordenação –– SelectionSelection SortSort
17
Algoritmos de Ordenação Algoritmos de Ordenação –– SelectionSelection SortSort
Complexidade deste algoritmo: O(n2)
void selectionSort(int tam, int *vetor)
{
int i, j, iMin, temp;
for(i=0;i<tam-1;i++)
{
iMin = i;
for (j=i+1; j<tam;j++)
{
if (vetor[j] < vetor[iMin])
{
iMin = j;
}
8/26/2014Footer Text 19
}
}
temp = vetor[i];
vetor[i]=vetor[iMin];
vetor[iMin] = temp;
}
}
Algoritmos de Ordenação Algoritmos de Ordenação –– SelectionSelection SortSort
20
Algoritmos de Ordenação Algoritmos de Ordenação ––
InsertionInsertion SortSort
• Definição
• A principal característica deste método consiste 
em ordenarmos o arranjo utilizando um sub-
arranjo ordenado localizado em seu inicio, e a 
cada novo passo, acrescentamos a este sub-
arranjo mais um elemento, até que atingimos o 
21
arranjo mais um elemento, até que atingimos o 
último elemento do arranjo fazendo assim com 
que ele se torne ordenado.
Algoritmos de Ordenação Algoritmos de Ordenação ––
InsertionInsertion SortSort
• Definição
• Analogamente as cartas de baralho, segure todas 
as cartas em sua mão. Ponha uma carta por vez na 
mesa, sempre inserindo-a na posição correta. O 
baralho estará ordenado sobre a mesa quando 
22
baralho estará ordenado sobre a mesa quando 
não houver mais cartas em sua mão.
Algoritmos de Ordenação Algoritmos de Ordenação –– InsertionInsertion SortSort
23
Algoritmos de Ordenação Algoritmos de Ordenação –– InsertionInsertion SortSort
Complexidade deste algoritmo: O(n2)
Algoritmos de Ordenação Algoritmos de Ordenação –– InsertionInsertion SortSort
25