Algoritmos1_Aula19-OrdenacaoDeVetor

Prévia do material em texto

Ordenação de vetor
Algoritmos I
Prof. Thiago Meirelles Ventura
UFMT – IC – 2013/1
Introdução
É de grande utilidade ter um vetor ordenado
Uma das razões é conseguir acessar com facilidade determinado elemento
Há várias formas de ordenar um vetor:
Inserção direta
Seleção direta
Por permutação
Inserção direta
Também chamada de “insertion sort”
Percorre um vetor de elementos e, a medida que avança, deixa os elementos mais à esquerda ordenados
Inserção direta
InsertionSort por Tiago Santos
Inserção direta
algoritmo InsercaoDireta
variáveis
 vet : vetor [1..10] de inteiro
 i, j, elemento : inteiro
início
 para i <- 1 até 10 faça
 leia (vet[i])
 fimpara
 para j <- 2 até 10 faça
 elemento <- vet[j]
 i <- j – 1
 enquanto ((i >= 1) e (vet[i] > elemento)) faça
 vet[i+1] <- vet[i]
 vet[i] <- elemento
 i <- i – 1
 fimenquanto
 fimpara
fim algoritmo
Seleção direta
Também chamada de “selection sort”
Se preocupa em passar o menor elemento para a primeira posição, depois o segundo menor elemento para a segunda posição, e assim por diante.
Seleção direta
SelectionSort por Tiago Santos
Seleção direta
algoritmo SelecaoDireta
variáveis
 vet : vetor [1..10] de inteiro
 i, j, aux, menor : inteiro
início
 [...] // leitura do vetor
 para i <- 1 até 9 faça
 menor <- i
 para j <- i+1 até 10 faça
 se (vet[menor] > vet[j]) então
 menor <- j
 fimse
 fimpara
 se (menor <> i) então
 aux <- vet[menor]
 vet[menor] <- vet[i]
 vet[i] <- aux
 fimse
 fimpara
fim algoritmo
Por permutação
Também chamada de “bubble sort” ou “bolha” ou “por troca”
Realizando várias iterações, movimenta os maiores valores para o final do vetor.
Por permutação
BubbleSort por Tiago Santos
Por permutação
algoritmo Bolha
variáveis
 vet : vetor [1..10] de inteiro
 i, j, k, aux : inteiro
início
 [...] // leitura do vetor
 k <- 9
 para i <- 1 até 10 faça
 j <- 1
 enquanto (j <= k) faça
 se (vet[j] > vet[j+1]) então
 aux <- vet[j]
 vet[j] <- vet[j+1]
 vet[j+1] <- aux
 fimse
 j <- j + 1
 fimenquanto
 k <- k - 1
 fimpara
fim algoritmo
Nova estrutura de repetição
Repita
Sintaxe:
Exemplos:
repita
 [...]
 comandos
 [...]
até que (condição)
i <- 1
repita
 escreva (i * 2)
 i <- i + 1
até que (i = 10)
Exercício 1
Faça um algoritmo que leia uma lista de 500 números, ordene-os pelo método da inserção direta, e diga, ao final:
Quantas trocas foram realizadas no total para ordená-lo
Qual elemento mais “desceu” no processo
Qual foi o tamanho desta “descida”
Exercício 2
Faça um algoritmo que leia uma lista de 500 números, ordene-os pelo método da seleção direta, e diga, ao final:
Quantas trocas foram realizadas no total para ordená-lo
Qual elemento mais “desceu” no processo
Qual foi o tamanho desta “descida”
Exercício 3
Faça um algoritmo que leia uma lista de 500 números, ordene-os pelo método da bolha, e diga, ao final:
Quantas trocas foram realizadas no total para ordená-lo
Em qual iteração houve mais trocas
Quantas trocas foram realizadas na iteração do item anterior