Ordenação

O objetivo deste capítulo é descrever um método de ordenação de dados. Estaremos ordenando um conjunto de dados em um vetor (que pode ter sido, por exemplo, copiado de uma coluna da planilha). Existem vários métodos de ordenação, e nós vamos nos concentrar no método de Ordenação por Bolhas.

Uma bolha nada mais é que um par de números ordenados, por exemplo, ( 2, 7 ) ou ( 7, 4 ). A primeira destas bolhas está ordenada crescentemente, enquanto a segunda não. Toda vez que encontrarmos uma bolha desordenada, vamos invertê-la, transformando ( 7, 4 ) em ( 4, 7 ).

As bolhas são assim chamadas pois ``sobem pela seqüência'' da mesma forma como bolhas de gas na água. Vamos explicar o método através de um exemplo. Suponhamos que nós queremos ordenar a seqüência 4,2,12,7,4,1 de 6 elementos. Um passo de ordenação pelo método de bolhas irá produzir as seguintes alterações nos dados:

12 7 4 1

2 (4 12) 7 4 1

2 4 (12 7) 4 1

2 4 7 (12 4) 1

2 4 7 4 (12 1)

2 4 7 4 1 12

O passo de ordenação faz uma bolha deslocar-se pelo vetor da esquerda para a direita, ordenando a bolha se esta estiver desordenada e, em seguinda, movendo a bolha para a direita. As bolhas acima aparecem entre parênteses e, quando estão desordenadas, também estão em negrito.

Note que o maior número da seqüência, 12, foi parar na posição mais à direita. Portanto, se realizarmos o passo de ordenação uma segunda vez, o segundo maior número, 7, irá parar na segunda posição à direita.

(2 4) 7 4 1 12

2 (4 7) 4 1 12

2 4 (7 4) 1 12

2 4 4 (7 1) 12

2 4 4 1 (7 12)

2 4 4 1 7 12

Se realizarmos este passo de ordenação N vezes, onde N é o número de elementos na seqüência, a seqüência estará ordenada.

Para implementar a ordenação pelo método de bolhas, utilizaremos as rotinas ColVet e VetCol do capítulo anterior, para realizar a leitura de uma coluna da planilha para um vetor e para realizar a cópia do vetor ordenado de volta para a planilha.

Para que o programa possa rodar, precisaremos copiar ColVet e VetCol no mesmo módulo que a macro principal, chamada de OrdenaCol. A coluna a ordenar é solicitada ao usuário.

Const TamVet = 20
Const LinhaInicial = 2

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

Em seguida, vamos detalhar a rotina OrdenaPorBolhas(tam, vetor()), que realiza a ordenação por bolhas. Na chamada da rotina o vetor não está ordenado mas, por efeitos colaterais, no seu término o vetor estará em ordem crescente.

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

Para finalizar, basta detalhar o passo de ordenação, que também recebe como parâmetros o tamanho do vetor e o vetor. Esta rotina também funciona por efeito colateral, devolvendo o vetor alterado por um passo de ordenação por bolhas.

Note que a inversão da bolha necessita de uma variável auxiliar.

Sub PassoOrdenação(nPos As Integer, vet() As Double)
'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
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

Exercícios

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.

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.

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.