4 - Ordenacao de Listas Lineares Sequenciais

Prévia do material em texto

Aula 3 
Ordenação de Listas Lineares Sequenciais 
 
prof Leticia Winkler 
 
1 
Selection Sort 
 Método da Seleção 
 Algoritmo: 
 Busca o menor elemento no vetor e troca com o 
elemento na primeira posição. Busca o segundo menor 
elemento no vetor e troca com o elemento na segunda 
posição e assim sucessivamente. 
 Supondo um vetor de inteiros de tamanho 9: 
 
Prof. Leticia Winkler 2 
25 46 32 23 37 41 17 10 53 
Mecanismo do Selection Sort 
 
 Procura o menor: 
 inicialmente o espaço de busca é todo o vetor 
 
 
 Troca com o elemento da posição 0 (zero) 
 
 
Prof. Leticia Winkler 3 
25 46 32 23 37 41 17 10 53 
25 46 32 23 37 41 17 10 53 
25 46 32 23 37 41 17 10 53 
25 46 32 23 37 41 17 53 10 
Espaço de busca 
Mecanismo do Selection Sort 
 Procura o segundo menor: 
 
 
 Troca com o elemento da posição 1 
 
 
 
 E assim por diante 
Prof. Leticia Winkler 4 
25 46 32 23 37 41 17 53 10 
25 46 32 23 37 41 17 53 10 
Espaço de busca 
Mecanismo do Selection Sort 
Prof. Leticia Winkler 5 
17 46 32 23 37 41 25 53 10 
17 46 32 23 37 41 25 53 10 
17 23 32 46 37 41 25 53 10 
Espaço de busca 
Mecanismo do Selection Sort 
Prof. Leticia Winkler 6 
17 23 32 46 37 41 25 53 10 
17 23 32 46 37 41 25 53 10 
17 23 25 46 37 41 32 53 10 
Espaço de busca 
Mecanismo do Selection Sort 
Prof. Leticia Winkler 7 
17 23 25 46 37 41 32 53 10 17 23 25 32 37 41 46 53 10 
17 23 25 46 37 41 32 53 10 
17 23 25 46 37 41 32 53 10 
Espaço de busca 
Mecanismo do Selection Sort 
Prof. Leticia Winkler 8 
Espaço de busca 
17 23 25 46 37 41 32 53 10 17 23 25 32 37 41 46 53 10 
17 23 25 46 37 41 32 53 10 17 23 25 32 37 41 46 53 10 
17 23 25 46 37 41 32 53 10 17 23 25 32 37 41 46 53 10 
Mecanismo do Selection Sort 
Prof. Leticia Winkler 9 
Espaço de busca 
17 23 25 46 37 41 32 53 10 17 23 25 32 37 41 46 53 10 
17 23 25 46 37 41 32 53 10 17 23 25 32 37 41 46 53 10 
17 23 25 46 37 41 32 53 10 17 23 25 32 37 41 46 53 10 
Mecanismo do Selection Sort 
Prof. Leticia Winkler 
10 
Espaço de busca 
17 23 25 46 37 41 32 53 10 17 23 25 32 37 41 46 53 10 
17 23 25 46 37 41 32 53 10 17 23 25 32 37 41 46 53 10 
17 23 25 46 37 41 32 53 10 17 23 25 32 37 41 46 53 10 
Vetor Ordenado !!! 
Animação do Selection Sort 
Prof. Leticia Winkler 11 
http://www.cs.oswego.edu/~mohammad/classes/csc241/sa
mples/sort/Sort2-E.html 
Código do Selection Sort 
void ordenaSelecao(int v[], int n) { 
 int i, j, menor, aux; 
 for (j = 0; j < n-1; j++) { 
 menor = j; 
 for (i = j+1; i < n; i++) 
 if (v[i] < v[menor]) 
 menor = i; 
 // faz a troca usando uma variável auxiliar 
 aux = v[j]; 
 v[j] = v[menor]; 
 v[menor] = aux; 
 } 
} 
 
Prof. Leticia Winkler 12 
Insertion Sort 
 Algoritmo: 
 Considera que o primeiro elemento está ordenado (ou seja, na 
posição correta). 
 A partir do segundo elemento, insere os demais elementos na 
posição apropriada entre aqueles já ordenados. 
 O elemento é inserido na posição adequada movendo-se todos os 
elementos maiores para posição seguinte do vetor. 
 Supondo um vetor de inteiros de tamanho 9: 
 
Prof. Leticia Winkler 13 
25 46 32 23 37 41 17 10 53 
Mecanismo do Insertion Sort 
 O primeiro elemento já está ordenado: 
 
 
 Guarda na variável auxiliar o valor em análise: 
 
 
 Compara com o trecho do vetor já ordenado, 
 Move as maiores para direita 
 
 
 Insere valor da auxiliar 
 
 Prof. Leticia Winkler 14 
25 46 32 23 37 41 17 10 53 
53 46 32 23 37 41 17 10 53 25 
aux 
53 46 32 23 37 41 17 10 25 25 
aux 
25 46 32 23 37 41 17 10 53 25 
aux 
Mecanismo do Insertion Sort 
 Guarda na variável auxiliar o valor em análise: 
 
 
 Compara com o trecho do vetor já ordenado, 
 Move as maiores para direita 
 
 
 Insere valor da auxiliar 
 
Prof. Leticia Winkler 15 
46 53 32 23 37 41 17 10 25 46 
aux 
46 
aux 
53 46 32 23 37 41 17 10 25 
46 
aux 
53 53 32 23 37 41 17 10 25 
Mecanismo do Insertion Sort 
 Guarda na variável auxiliar o valor em análise: 
 
 
 Compara com o trecho do vetor já ordenado, 
 Move as maiores para direita 
 
 
 
 Insere valor da auxiliar 
 
Prof. Leticia Winkler 16 
32 46 53 23 37 41 17 10 25 
32 
aux 
32 
aux 
46 53 32 23 37 41 17 10 25 
46 53 53 23 37 41 17 10 25 
46 46 53 23 37 41 17 10 25 
32 
aux 
Mecanismo do Insertion Sort 
 Guarda na variável auxiliar o valor em análise: 
 
 Compara com o trecho do vetor já ordenado, 
 Move as maiores para direita 
 
 
 
 
 
Prof. Leticia Winkler 17 
23 
aux 
32 46 53 23 37 41 17 10 25 
23 
aux 
32 46 53 53 37 41 17 10 25 
32 46 46 53 37 41 17 10 25 
32 32 46 53 37 41 17 10 25 
25 32 46 53 37 41 17 10 25 
Mecanismo do Insertion Sort 
 Insere valor da auxiliar 
 
 
Prof. Leticia Winkler 18 
25 32 46 53 37 41 17 10 23 23 
aux 
Mecanismo do Insertion Sort 
 Guarda na variável auxiliar o valor em análise: 
 
 Compara com o trecho do vetor já ordenado, 
 Move as maiores para direita 
 
 
 
 Insere valor da auxiliar 
 
Prof. Leticia Winkler 19 
37 
aux 
37 
aux 
25 32 46 53 37 41 17 10 23 
25 32 46 53 53 41 17 10 23 
37 
aux 
25 32 37 46 53 41 17 10 23 
25 32 46 46 53 41 17 10 23 
Mecanismo do Insertion Sort 
 Guarda na variável auxiliar o valor em análise: 
 
 Compara com o trecho do vetor já ordenado, 
 Move as maiores para direita 
 
 
 
 Insere valor da auxiliar 
 
Prof. Leticia Winkler 20 
41 
aux 
25 32 37 46 53 41 17 10 23 
41 
aux 
25 32 37 46 53 53 17 10 23 
25 32 37 46 46 53 17 10 23 
41 
aux 
25 32 37 41 46 53 17 10 23 
Mecanismo do Insertion Sort 
 Guarda na variável auxiliar o valor em análise: 
 
 Compara com o trecho do vetor já ordenado, 
 Move as maiores para direita 
 
 
 
 
Prof. Leticia Winkler 21 
17 
aux 
17 
aux 
25 32 37 41 46 53 17 10 23 
25 32 37 41 46 53 53 10 23 
25 32 37 37 41 46 53 10 23 
25 32 37 41 46 46 53 10 23 
25 32 37 41 41 46 53 10 23 
25 32 32 37 41 46 53 10 23 
Mecanismo do Insertion Sort 
 Move as maiores para direita 
 
 
 
 
 
 Insere valor da auxiliar 
 
 
 
 
 
Prof. Leticia Winkler 22 
17 
aux 
25 25 32 37 41 46 53 10 23 
23 25 32 37 41 46 53 10 23 
17 
aux 
23 25 32 37 41 46 53 10 17 
Mecanismo do Insertion Sort 
 Guarda na variável auxiliar o valor em análise: 
 
 
 Compara com o trecho do vetor já ordenado, 
 Move as maiores para direita 
 
 
 
 
Prof. Leticia Winkler 
10 
aux 
23 25 32 37 41 46 53 10 17 
10 
aux 
23 25 32 37 41 46 53 53 17 
23 25 32 37 41 46 46 53 17 
23 25 32 37 41 41 46 53 17 
23 25 32 37 37 41 46 53 17 
Mecanismo do Insertion Sort 
 Move as maiores para direita 
 
 
 
 
 
 
 Insere valor da auxiliar 
 
 
Prof. Leticia Winkler 24 
10 
aux 
23 25 32 32 37 41 46 53 17 
23 25 25 32 37 41 46 53 17 
23 23 25 32 37 41 46 53 17 
17 23 25 32 37 41 46 53 17 
10 
aux 
17 23 25 32 37 41 46 53 10 
Vetor Ordenado !!! 
Animação do Insertion Sort 
http://www.cs.oswego.edu/~mohammad/classes/cs
c241/samples/sort/Sort2-E.html 
 
Prof. Leticia Winkler 25 
Código do Insertion Sort 
void ordenaInsercao(int v[], int n) { 
 // n é o número de elementos em v 
 int i, j, aux; 
 for (j = 1; j < n; j++) { 
 aux = v[j]; 
 for (i=j; i > 0 && v[i-1]> aux; i--) { 
 v[i] = v[i-1]; 
 } 
 v[i] = aux; 
 } 
} 
Prof. Leticia Winkler 26 
Prof. Leticia Winkler 27 
Exercício #1 
void ordena (int p[], int t) { 
 int i, j, aux; 
 for (i = 1; i < t; i++) { 
 aux = p[i]; 
 j = i; 
 while (j>0 && p[j-1] > aux) { 
 p[j] = p[j-1]; 
 j--; 
 } 
 p[j] = aux; 
 } 
} 
void ordena (int v[], int n) { 
 int i, j, aux; 
 for (j = 0; j < n; j++){for (i=j; i >= 0 && v[i-1]> v[i]; i--) { 
 aux = v[i-1]; 
 v[i-1] = v[i]; 
 v[i] = aux; 
 } 
 } 
} 
 
Prof. Leticia Winkler 28 
 As funções abaixo realizam o mesmo método de ordenação? 
Prof. Leticia Winkler 29 
Questão #1 
Prova: CESPE - 2008 - TRT - 5ª Região (BA) - Analista Judiciário - Tecnologia da Informação 
(adapatado para C/C++) 
 for (j = 1; j<tamanhoVetor; j++) { 
 chave = vetor[j]; 
 i = j – 1; 
 while (i >= 0 && vetor[i] > chave) { 
 vetor [i+1] = vetor [i]; 
 i--; 
 } 
 vetor[i+1] = chave; 
 } 
 Com relação ao código acima, julgue o item a seguir. 
 Esse código varre um vetor de elementos desde o menor índice até o maior 
índice e a medida que avança, vai deixando os elementos com menor índice 
ordenados. 
 ( ) Certo ( )Errado 
 
Prof. Leticia Winkler 30 
Questão #2 
... 
for (i=0 ; i < n; i++) { 
 j= i+1; 
 aux= i; 
 while (j < n) { 
 if (v[j] < v[aux]) { 
 aux = j; 
 } 
 j++; 
 } 
 x= v[i]; 
 v[i]= v[aux]; 
 v[aux]= x; 
} 
... 
 
UFMT – Técnico de Tecnologia da Informação – 2008 
(adaptado para linguagem C/C++) 
 Analise o trecho de algoritmo de ordenação 
de dados ao lado, cujos elementos estão 
dispostos em um vetor entre as posições 0 e 
n-1 inclusive. 
Assinale o método ao qual o trecho de 
algoritmo pertence. 
A) Bolha (permutação) 
B) Quick-sort 
C) Seleção direta 
D) Inserção direta 
E) Heap-sort 
 
Prof. Leticia Winkler 31 
Questão #3 
void ordena(int vetor [], int n){ 
 for (int i = 0; i < n; i++) { 
 for (int j = i; j > 0; j--) { 
 if (vetor[j-1] > vetor[j]) { 
 int temp = vetor[j]; 
 vetor[j] = vetor[j-1]; 
 vetor[j-1] = temp; 
 } 
 } 
 } 
} 
 
BANPARÁ – TÉC. INF. – DESENVOLVIMENTO DE 
SISTEMA E ACOMPANHAMENTO DE PROJETO – 2008 
 Foi solicitada a implementação 
de um método de ordenação de 
vetores. O resultado 
apresentado foi o trecho ao lado: 
(adaptado para C/C++) 
Que método foi implementado no 
código anterior? 
a) Ordenação por seleção. 
b) Ordenação por quicksort. 
c) Ordenação por heapsort. 
d) Ordenação por inserção. 
 
Prof. Leticia Winkler 32 
Questão #4 
void Sort (int v[], int n) { 
 for (int i = n - 1; i > 0; i-- ) { 
 for (int j = 0; j < i; j++) 
 if (v [j] > v [j + 1]) 
 swaper (v, j, j + 1); 
 } 
} 
void swaper (int v[], int j, int aposJ) { 
 int aux = 0; 
 aux = v [j]; 
 v [j] = v [aposJ]; 
 v [aposJ] = aux; 
} 
 
TRENSURB – Analista de Sistemas 
Considere o código ao lado: 
(adaptado para C/C++) 
 Indique que método de 
ordenação está implementado. 
a) Quick Sort 
b) Bubble Sort 
c) Heapsort 
d) Shell Sort 
e) Merge Sort 
 
Prof. Leticia Winkler 33 
Questão #5 
IDARON – Analista de Sistemas – 2009 
 O método de ordenação que compara pares de chaves 
de ordenação, trocando os elementos correspondentes 
caso estejam fora de ordem é o método: 
A) por inserção; 
B) por seleção; 
C) por troca ou bolha; 
D) por distribuição; 
E) QuickSort. 
 
 
Prof. Leticia Winkler 34 
Questão #6 
ANAC - Técnico Administrativo – Informática - 2009 
O desempenho de um sistema computacional depende 
de vários fatores, como volume de dados, capacidade do 
sistema e adequação dos algoritmos, das estruturas de 
dados e dos objetos que são utilizados para realizar as 
operações. Acerca desse assunto, julgue o item a seguir. 
 A ordenação de um vetor contendo n elementos, 
utilizando-se algoritmo de bolha, realiza, no pior caso, 
mais que n/2 comparações. 
( ) Certo ( ) Errado 
 
Prof. Leticia Winkler 35 
Questão #7 
CELEPAR •. CARGO DE: TÉCNICO JÚNIOR / PROGRAMAÇÃO • 12 / MARÇO / 2006 
O método bubble-sort (bolha) de classificação de dados contidos em um vetor (array) consiste 
em: 
A) arbitrar um registro de pivô, posicionar os registros de maior ordem à direita e os de menor 
ordem à esquerda do pivô e aplicar o algoritmo recursivamente para os dois sub-vetores 
formados à esquerda e direita do pivô, respectivamente. 
Repetir o procedimento até que os sub-vetores possuam um único registro. 
B) inserir cada registro do vetor original na primeira posição disponível de um vetor auxiliar 
inicialmente vazio. Trocar registros adjacentes, iniciando-se com o mais recentemente inserido 
e avançando em direção ao primeiro registro do vetor auxiliar, enquanto os registros 
adjacentes estiverem fora de ordem. Copiar o conteúdo do vetor auxiliar para o vetor original. 
C) arbitrar um incremento inicial e agrupar os registros do vetor original em subgrupos 
contendo os registros de índice j, j+i, j+2i,..., onde i é o incremento arbitrado. Ordenar cada um 
dos subgrupos conforme o método exposto na alternativa 
b). Repetir o procedimento, diminuindo o valor do incremento até 1. 
D) trocar os pares de registros adjacentes no vetor original, caso estejam fora de ordem, até 
chegar ao último par do vetor original. 
E) iniciando pelo primeiro registro, trocar os pares de registros adjacentes no vetor original, 
caso estejam fora de ordem, até chegar ao último par do vetor original. Repetir o procedimento 
considerando-se um sub-vetor que é igual ao vetor anterior menos o seu último registro (que já 
está na posição correta), até que o sub-vetor possua somente 1 registro. 
Prof. Leticia Winkler 36 
Questão #8 
CESPE - 2010 - TRE-BA - Analista Judiciário - Análise de Sistemas 
 Vetores podem ser considerados como listas de 
informações armazenadas em posição contígua na 
memória. 
( ) Certo ( ) Errado 
 
Prof. Leticia Winkler 37 
Questão #10 
CESPE - 2010 - TRE-BA - Analista Judiciário - Análise de Sistemas 
 O uso de vetores deve ser evitado em situações em que 
um conjunto de dados do mesmo tipo precisa ser 
armazenado em uma mesma estrutura. 
( ) Certo ( )Errado 
 
Prof. Leticia Winkler 38 
Questão #11 
CESPE - 2010 - TRE-BA - Analista Judiciário - Análise de Sistemas 
 Uma posição específica de um vetor pode ser acessada 
diretamente por meio de seu índice. 
( ) Certo ( )Errado 
 
Prof. Leticia Winkler 39 
Questão #12 
 A classificação interna por inserção é um método que 
realiza a ordenação de um vetor por meio da inserção 
de cada elemento em sua posição correta dentro de um 
subvetor classificado. 
( ) Certo ( ) Errado 
 
Prof. Leticia Winkler 40 
Exercício 
 Faça um programa para criar uma lista linear seqüencial não 
ordenada de inteiros pares e oferecer um menu com as seguintes 
opções : 
 Inserção na lista 
 Percorrer a lista 
 Ordenação por troca (Bubblesort) 
 Ordenação por seleção 
 Ordenação por inserção 
 Obs: 
 Para cada operação deve ser criada uma função. 
 Que alterações devem ser feitas nas funções de ordenação, para 
que os elementos fiquem em ordem decrescente? 
Prof. Leticia Winkler 41