Aula13 - Programação (VBA)

Prévia do material em texto

Introdução à Computação
Para Ciências Humanas
10 semestre de 2017
Renata Wassermann
renata@ime.usp.br
(slides adaptados do Prof. Gerosa, que adaptou do Prof. Paulo Feofiloff)
 
Ordenação
Permutar (ou seja, rearranjar) os elementos de um 
vetor v(n) de tal modo que eles fiquem em ordem 
crescente, isto é, de tal forma que tenhamos: 
v(0) ≤ v(1) ≤ . . . ≤ v(n-1) 
Ordenação
• A ordenação facilita no processo de busca de 
alguma informação dentro de um conjunto de dados
xistem muitos algoritmos de ordenação como o 
Bubble Sort, Selection Sort, Quicksort, Mergesort, 
Insertion Sort, Shellsort, Heapsort
Dependendo da situação, um pode ser mais rápido 
do que outro
Marco A. Gerosa 3 IME / USP
Ordenação
• A ordenação facilita no processo de busca de 
alguma informação dentro de um conjunto de dados
• Existem muitos algoritmos de ordenação como o 
Bubble Sort, Selection Sort, Quicksort, Mergesort, 
Insertion Sort, Shellsort, Heapsort
Dependendo da situação, um pode ser mais rápido 
do que outro
Marco A. Gerosa 4 IME / USP
Ordenação
• A ordenação facilita no processo de busca de 
alguma informação dentro de um conjunto de dados
• Existem muitos algoritmos de ordenação como o 
Bubble Sort, Selection Sort, Quicksort, Mergesort, 
Insertion Sort, Shellsort, Heapsort
• Dependendo da situação, um pode ser mais rápido 
do que outro
Marco A. Gerosa 5 IME / USP
Ordenação: Método Bolha
O método consiste em ordenar pares de dados:
Primeiro, comparamos o primeiro elemento com o 
segundo. Como vet(1) > vet(2), invertemos os dois:
Marco A. Gerosa 6 IME / USP
55 33 66 22 11
1 2 3 4 5
vet
vet
Ordenação: Método Bolha
O método consiste em ordenar pares de dados:
Primeiro, comparamos o primeiro elemento com o 
segundo. Como vet(1) > vet(2), invertemos os dois:
Marco A. Gerosa 7 IME / USP
55 33 66 22 11
1 2 3 4 5
vet
33 55 66 22 11
1 2 3 4 5
vet
Ordenação: Método Bolha
Depois, compara-se o segundo com o terceiro, o terceiro 
com o quarto, e assim sucessivamente. Quando chegar ao 
final do vetor, o maior elemento estará na última posição. 
Marco A. Gerosa 8 IME / USP
33 55 66 22 11
1 2 3 4 5
vet
vet
vet
vet
55 > 66? Não, logo, não inverte.
66 > 22? Sim, logo, inverte.
66 > 11? Sim, logo, inverte.
Ordenação: Método Bolha
Depois, compara-se o segundo com o terceiro, o terceiro 
com o quarto, e assim sucessivamente. Quando chegar ao 
final do vetor, o maior elemento estará na última posição. 
Marco A. Gerosa 9 IME / USP
33 55 66 22 11
1 2 3 4 5
vet
33 55 66 22 11
1 2 3 4 5
vet
vet
vet
55 > 66? Não, logo, não inverte.
66 > 22? Sim, logo, inverte.
66 > 11? Sim, logo, inverte.
Ordenação: Método Bolha
Depois, compara-se o segundo com o terceiro, o terceiro 
com o quarto, e assim sucessivamente. Quando chegar ao 
final do vetor, o maior elemento estará na última posição. 
Marco A. Gerosa 10 IME / USP
33 55 66 22 11
1 2 3 4 5
vet
33 55 66 22 11
1 2 3 4 5
vet
33 55 22 66 11
1 2 3 4 5
vet
vet
55 > 66? Não, logo, não inverte.
66 > 22? Sim, logo, inverte.
66 > 11? Sim, logo, inverte.
Ordenação: Método Bolha
Depois, compara-se o segundo com o terceiro, o terceiro 
com o quarto, e assim sucessivamente. Quando chegar ao 
final do vetor, o maior elemento estará na última posição. 
Marco A. Gerosa 11 IME / USP
33 55 66 22 11
1 2 3 4 5
vet
33 55 66 22 11
1 2 3 4 5
vet
33 55 22 66 11
1 2 3 4 5
vet
33 55 66 11 66
1 2 3 4 5
vet
55 > 66? Não, logo, não inverte.
66 > 22? Sim, logo, inverte.
66 > 11? Sim, logo, inverte.
Ordenação: Método Bolha
Para trocar dois valores de lugar, podemos chamar uma 
macro e informar onde os valores estão e quais serão 
invertidos:
Marco A. Gerosa 12 IME / USP
33 55 66 22 11
1 2 3 4 5
vet
66 > 22? Sim, logo, inverte.
Sub troca(vet() As Integer, i As Integer, _
                            j As Integer)
    Dim aux As Integer
    aux = vet(i)
    vet(i) = vet(j)
    vet(j) = aux
End Sub
Ordenação: Método Bolha
Para um vetor de 5 posições, fazemos 4 comparações: 
Note que o vetor ainda não está ordenado. A única coisa 
que foi feita foi colocar o maior valor na última posição
Marco A. Gerosa 13 IME / USP
33 55 66 11 66
1 2 3 4 5
vet
For j = 1 To tam ­ 1
       If vet(j) > vet(j + 1) Then
              Call troca(vet, j, j + 1)
       End If
Next
Ordenação: Método Bolha
Se repetirmos o laço do slide anterior mais uma 
vez, teremos o segundo maior valor na penúltima 
posição. Depois, o terceiro maior valor na 
antepenúltima posição e assim por diante, ou seja, 
precisamos repetir o laço n vezes.
Marco A. Gerosa 14 IME / USP
Ordenação: Método Bolha
Marco A. Gerosa 15 IME / USP
Sub ordena_bolha(vet() As String, _
                 tam As Integer)
    Dim i As Integer
    Dim j As Integer
    i = 1
    While i < tam
         For j = 1 To tam ­ 1
            If vet(j) > vet(j + 1) Then
                Call troca(vet, j, j + 1)
            End If
         Next
         tam = tam ­ 1
    Wend
End Sub
 
Ordenação: Método Bolha
Percorre o vetor n vezes (O(n²)).
O que acontece se o vetor já estiver 
ordenado, ou quase?
Solução: aviso de troca.
 
Ordenação: Método Bolha
Percorre o vetor n vezes (O(n²)).
O que acontece se o vetor já estiver 
ordenado, ou quase?
Solução: aviso de troca.
 
Ordenação: Método Bolha
Percorre o vetor n vezes (O(n²)).
O que acontece se o vetor já estiver 
ordenado, ou quase?
Solução: aviso de troca.
Método Bolha com Aviso de Troca
Marco A. Gerosa 19 IME / USP
Sub ordena_bolha(vet() As String, _
                 tam As Integer)
    Dim j As Integer
    Dim trocou As Boolean
    trocou = True
    While trocou
         trocou = False
         For j = 1 To tam ­ 1
            If vet(j) > vet(j + 1) Then
                Call troca(vet, j, j + 1)
                trocou = True
            End If
         Next
    Wend
End Sub
Ordenação: Método de Seleção
• No Método Bolha, cada vez que um elemento é encontrado 
fora do lugar, ele muda de posição.
• No Método de Seleção, existe uma pequena modificação 
que pode gerar uma diferença grande como resultado final.
• Neste método, a posição do maior valor é guardada e, ao 
final do laço, os valores são trocados de posição uma única 
vez.
Marco A. Gerosa 20 IME / USP
Ordenação: Selection Sort
Marco A. Gerosa 21 IME / USP
Sub ordena_selection(vet() As Integer, _
                     tam As Integer)
   Dim i As Integer
   Dim j As Integer
   Dim pos As Integer
   i = 1
   While i < tam
        pos = 1
        For j = 1 To tam ­ 1
           If vet(j + 1) > vet(pos) Then: _
               pos = j + 1
        Next
        Call troca(vet, tam, pos)
        tam = tam ­ 1
   Wend
End Sub
posição é inicializada
Ordenação: Selection Sort
Marco A. Gerosa 22 IME / USP
Sub ordena_selection(vet() As Integer, _
                     tam As Integer)
   Dim i As Integer
   Dim j As Integer
   Dim pos As Integer
   i = 1
   While i < tam
        pos = 1
        For j = 1 To tam ­ 1
           If vet(j + 1) > vet(pos) Then: _
               pos = j + 1
        Next
        Call troca(vet, tam, pos)
        tam = tam ­ 1
   Wend
End Sub
posição é inicializada
posição do maior 
valor é guardada
Ordenação: Selection Sort
Marco A. Gerosa 23 IME / USP
Sub ordena_selection(vet() As Integer, _
                     tam As Integer)
   Dim i As Integer
   Dim j As Integer
   Dim pos As Integer
   i = 1
   While i < tam
        pos = 1
        For j = 1 To tam ­ 1
           If vet(j + 1) > vet(pos) Then: _
               pos = j + 1
        NextCall troca(vet, tam, pos)
        tam = tam ­ 1
   Wend
End Sub
posição é inicializada
posição do maior 
valor é guardada
A troca é feita 
uma única vez
Exercício
Crie um vetor de inteiros aleatórios e organize-os 
em ordem crescente. Leia da Célula A1 o número 
de elementos n do vetor e depois coloque na Linha 
2 os elementos ordenados.
num = Cint(Math.Floor(n * Rnd())) + 1
Marco A. Gerosa 24 IME / USP
	Slide 1
	Slide 2
	Ordenação
	Slide 4
	Slide 5
	Ordenação: Método Bolha
	Slide 7
	Ordenação: Método Bolha
	Slide 9
	Slide 10
	Slide 11
	Ordenação: Método Bolha
	Ordenação: Método Bolha
	Slide 14
	Ordenação: Método Bolha
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Ordenação: Selection Sort
	Ordenação: Selection Sort
	Slide 22
	Slide 23
	Slide 24