Baixe o app para aproveitar ainda mais
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
Compartilhar