Upload
phamngoc
View
223
Download
0
Embed Size (px)
Citation preview
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/samples/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/csc241/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