Resolução dos Exercícios

Capítulo 12
Ordenação

1. Alterar o programa de ordenação acima para gerar a coluna em ordem decrescente. Note que para isso basta alterar uma linha do passo de ordenação.

Resolução:

Iremos utilizar a função ColVet e a macro VetCol descritas no capítulo anterior.

Const TamVet = 20
Const LinhaInicial = 1

Sub OrdenaCol()

    Dim colAOrdenar As Integer 'Coluna a ordenar
    Dim vetorColuna(TamVet) As Double 'vetor que abriga a coluna
    Dim tamCol As Integer 'numero de elementos a serem ordenados

    colAOrdenar = CInt(InputBox("Qual a coluna a ser ordenada?"))

    'Lê a coluna
    tamCol = ColVet(colAOrdenar, vetorColuna(), LinhaInicial, TamVet)

    'Ordena a coluna
    Call OrdenaPorBolhas(tamCol, vetorColuna())

    'Escreve a coluna ordenada
    Call VetCol(colAOrdenar, vetorColuna(), LinhaInicial, tamCol)

End Sub

Sub OrdenaPorBolhas(tam As Integer, vet() As Double)

    'Ordena o vetor vet() de tam posições pelo
    ' método das bolhas. Ao final, vet() está ordenado
    Dim vez As Integer 'Número de vezes que se repete o passo de ordenação
    vez = 1

    'Repete (tam - 1) vezes, pois vetor de tamanho 1 já está ordenado
    Do While vez <= tam - 1
        Call PassoOrdenação(tam, vet())
        vez = vez + 1
    Loop

End Sub

Sub PassoOrdenação(nPos As Integer, vet() As Integer)

    'Passo de Ordenação do vetor vet.
    ' Ao fim da execução da rotina, o maior valor
    ' de vet está na posição de maior índice (nPos).
    Dim i As Integer 'Indice do vetor
    Dim aux As Double 'Auxiliar na inversão da bolha

    i = 1 'Primeira posição

    'Repita a inversão da bolha (nPos -1) vezes
    Do While i <= nPos - 1

        'Verifica se a bolha é inversível
        'Neste ponto faremos a modificação para ordenar o vetor em
        'ordem decrescente
        'Linha original: If vet(i) > vet(i + 1) Then
        If vet(i) < vet(i + 1) Then
            'Inverte a bolha
            aux = vet(i)
            vet(i) = vet(i + 1)
            vet(i + 1) = aux
        End If

        i = i + 1 'Próxima bolha
    Loop

End Sub

2. O passo de ordenação do método de bolhas garante que o maior valor da seqüência estará à direita. Não há necessidade, portanto, de se considerar este valor no próximo passo de ordenação, uma vez que ele já está em sua posição definitiva.

No exemplo acima, o primeiro passo produziu:

2 4 7 4 1 12

onde 12 foi parar na posição final e definitiva. O segundo passo produziu

2 4 4 1 7 12

onde 7 foi parar na posição definitiva (e 12 permaneceu na mesma posição).

Altere o programa para, a cada passo, propagar a bolha até uma posição a menos que na vez anterior.

Dica: uma pequena alteração na rotina OrdenaPorBolhas() resolve o problema.

Resolução:

Sub OrdenaPorBolhas(tam As Integer, vet() As Double)

    'Ordena o vetor vet() de tam posições pelo
    ' método das bolhas. Ao final, vet() está ordenado
    Dim vez As Integer 'Número de vezes que se repete o passo de ordenação
    vez = 1

    'Repete (tam - 1) vezes, pois vetor de tamanho 1 já está ordenado
    Do While vez <= tam - 1
        'Precisamos mudar apenas a próxima linha
        'Linha original: Call PassoOrdenação(tam, vet())
        'A cada chamada da sub PassoOrdenação, informamos que o vetor tem um elemento a menos
        Call PassoOrdenação(tam + 1 - vez, vet())
        vez = vez + 1
    Loop

End Sub

3. Muitas vezes o vetor já está ordenado antes da execução dos Npassos de ordenação. Por exemplo, se o vetor já está ordenado de início, não há motivos para continuar aplicando os passos de ordenação.

Altere seu programa para que este pare de aplicar o passo de ordenação assim que a aplicação do passo de aplicação não realizar nenhuma inversão de ordem. O programa pode parar pois, garantidamente neste caso, o vetor já está ordenado.

Resolução:

Para resolvermos este exercício, iremos alterar a macro OrdenaPorBolhas apenas. Não precisaremos mais utilizar a função auxiliar PassoOrdenação.

Sub OrdenaPorBolhas(tam As Integer, vet() As Double)

    'Ordena o vetor vet() de tam posições pelo
    ' método das bolhas. Ao final, vet() está ordenado
    Dim vez As Integer 'Número máximo de vezes que se repete o passo de ordenação

    Dim i As Integer 'Indice do vetor
    Dim aux As Double 'Auxiliar na inversão da bolha

    'Criaremos uma variável que marcará se houve alguma inversão ou não
    'Se trocou = 1 houve inversão, se trocou = 0, não houve inversão
    Dim trocou As Integer

    vez = 1
    trocou = 1 'inicializamos com 1 só para entrarmos no loop

    'Repete no máximo (tam - 1) vezes, pois vetor de tamanho 1 já está ordenado
    'Se não realizar nenhuma inversão não repete mais nenhuma vez
    Do While vez <= tam - 1 And trocou = 1

         trocou = 0
         i = 1 'Primeira posição

         'Repita a inversão da bolha (tam + 1 - vez) vezes
         Do While i <= tam + 1 - vez

         'Verifica se a bolha é inversível
         If vet(i) < vet(i + 1) Then
             trocou = 1 'marca que houve inversão
             'Inverte a bolha
             aux = vet(i)
             vet(i) = vet(i + 1)
             vet(i + 1) = aux
         End If

         i = i + 1 'Próxima bolha
         Loop

         'Se neste ponto trocou = 0, temos certeza que o vetor está ordenado
         'portanto podemos sair do loop

    vez = vez + 1
    Loop

End Sub

[ Voltar ]