19 - Vectores - Ordenamiento de sus componentes


El ordenamiento de un vector se logra intercambiando las componentes de manera que:
vec(0) <= vec(1) <= vec(2) etc.

El contenido de la componente vec(0) sea menor o igual al contenido de la componente vec(1) y así sucesivamente.
Si se cumple lo dicho anteriormente decimos que el vector está ordenado de menor a mayor. Igualmente podemos ordenar un vector de mayor a menor.

Se puede ordenar tanto vectores con componentes de tipo Ingeger, Single como String. En este último caso el ordenamiento es alfabético.

Problema 1:

Se debe crear un vector donde almacenar 5 sueldos. Ordenar el vector sueldos de menor a mayor.

ordenamiento de un vector

Esta primera aproximación tiene por objetivo analizar los intercambios de elementos dentro del vector.

El algoritmo consiste en comparar si la primera componente es mayor a la segunda, en caso que la condición sea verdadera, intercambiamos los contenidos de las componentes.

Vamos a suponer que se ingresan los siguientes valores por teclado:

1200
750
820
550
490

En este ejemplo: ¿es 1200 mayor a 750? La respuesta es verdadera, por lo tanto intercambiamos el contenido de la componente 0 con el de la componente 1.
Luego comparamos el contenido de la componente 1 con el de la componente 2: ¿Es 1200 mayor a 820?
La respuesta es verdadera entonces intercambiamos.
Si hay 5 componentes hay que hacer 4 comparaciones, por eso el for se repite 4 veces.
Generalizando: si el vector tiene N componentes hay que hacer N-1 comparaciones.

Cuando		f = 0		f = 1		f  = 2		f = 3
		
		750		750		750		750
		1200		820		820		820
		820		1200		550		550
		550		550		1200		490
		490		490		490		1200

Podemos ver cómo el valor más grande del vector desciende a la última componente. Empleamos una variable auxiliar (aux) para el proceso de intercambio:

aux = sueldos(f)
sueldos(f) = sueldos(f+1)
sueldos(f+1) = aux

Al salir del For en este ejemplo el contenido del vector es el siguiente:

750
820
550
490
1200

Analizando el algoritmo podemos comprobar que el elemento mayor del vector se ubica ahora en el último lugar.
Podemos definir otros vectores con distintos valores y comprobar que siempre el elemento mayor queda al final.

Pero todavía con este algoritmo no se ordena un vector. Solamente está ordenado el último elemento del vector.

Ahora bien, con los 4 elementos que nos quedan podemos hacer el mismo proceso visto anteriormente, con lo cual quedará ordenado otro elemento del vector. Este proceso lo repetiremos hasta que quede ordenado por completo el vector.

Como debemos repetir el mismo algoritmo podemos englobar todo el bloque en otra estructura repetitiva.

ordenamiento de un vector

Realicemos una prueba del siguiente algoritmo:

Cuando k = 0
		f = 0		f = 1		f = 2		f = 3
		750		750		750		750
		1200		820		820		820
		820		1200		550		550
		550		550		1200		490
		490		490		490		1200
		
Cuando k = 1
		f = 0		f = 1		f  = 2		f = 3
		750		750		750		750	
		820		550		550		550
		550		820		490		490
		490		490		820		820
		1200		1200		1200		1200

Cuando k = 2
		f = 0		f = 1		f  = 2		f = 3
		550		550		550		550
		750		490		490		490
		490		750		750		750
		820		820		820		820
		1200		1200		1200		1200


Cuando k = 3
		f = 0		f = 1		f  = 2		f = 3
		490		490		490		490
		550		550		550		550
		750		750		750		750
		820		820		820		820
		1200		1200		1200		1200

¿Porqué repetimos 4 veces el For externo?
Como sabemos cada vez que se repite en forma completa el For interno queda ordenada una componente del vector. A primera vista diríamos que deberíamos repetir el For externo la cantidad de componentes del vector, en este ejemplo el vector sueldos tiene 5 componentes.

Si observamos, cuando quedan dos elementos por ordenar, al ordenar uno de ellos queda el otro automáticamente ordenado (podemos imaginar que si tenemos un vector con 2 elementos no se requiere el For externo, porque este debería repetirse una única vez)

Una última consideración a este ALGORITMO de ordenamiento es que los elementos que se van ordenando continuamos comparándolos.

Ejemplo: En la primera ejecución del For interno el valor 1200 queda ubicado en la posición 4 del vector. En la segunda ejecución comparamos si el 820 es mayor a 1200, lo cual seguramente será falso.
Podemos concluir que la primera vez debemos hacer para este ejemplo 4 comparaciones, en la segunda ejecución del For interno debemos hacer 3 comparaciones y en general debemos ir reduciendo en uno la cantidad de comparaciones.
Si bien el algoritmo planteado funciona, un algoritmo más eficiente, que se deriva del anterior es el plantear un For interno con la siguiente estructura: For f=0 To 3-k
Es decir restarle el valor del contador del For externo.

Programa:

Module Module1
    Public Class PruebaVector13

        Private sueldos(4) As Integer

        Public Sub Cargar()
            Dim f As Integer
            For f = 0 To 4
                Console.Write("Ingrese el sueldo:")
                sueldos(f) = Console.ReadLine()
            Next
        End Sub

        Public Sub Ordenar()
            Dim f, k As Integer
            For k = 0 To 3
                For f = 0 To 3 - k
                    If sueldos(f) > sueldos(f + 1) Then
                        Dim aux As Integer
                        aux = sueldos(f)
                        sueldos(f) = sueldos(f + 1)
                        sueldos(f + 1) = aux
                    End If
                Next
            Next
        End Sub

        Public Sub Imprimir()
            Console.WriteLine("Sueldos ordenados de menor a mayor.")
            For f = 0 To 4
                Console.WriteLine(sueldos(f))
            Next
            Console.ReadKey()
        End Sub
    End Class


    Sub Main()
        Dim pv As New PruebaVector13()
        pv.Cargar()
        pv.Ordenar()
        pv.Imprimir()
    End Sub

End Module

También podemos ordenar vectores cuyas componentes sean de tipo String. Para esto también utilizamos el operador >

Problema 2:

Definir un vector donde almacenar los nombres de 5 paises. Confeccionar el algoritmo de ordenamiento alfabético.

Programa:

Module Module1
    Public Class PruebaVector14

        Private paises(4) As String

        Public Sub Cargar()
            Dim f As Integer
            For f = 0 To 4
                Console.Write("Ingrese el nombre del pais:")
                paises(f) = Console.ReadLine()
            Next
        End Sub

        Public Sub Ordenar()
            Dim k, f As Integer
            For k = 0 To 3
                For f = 0 To 3 - k
                    If paises(f) > paises(f + 1) Then
                        Dim aux As String
                        aux = paises(f)
                        paises(f) = paises(f + 1)
                        paises(f + 1) = aux
                    End If
                Next
            Next
        End Sub

        Public Sub Imprimir()
            Console.WriteLine("Paises ordenados en forma alfabética:")
            Dim f As Integer
            For f = 0 To 4
                Console.WriteLine(paises(f))
            Next
            Console.ReadKey()
        End Sub
    End Class


    Sub Main()
        Dim pv As New PruebaVector14()
        pv.Cargar()
        pv.Ordenar()
        pv.Imprimir()
    End Sub

End Module

Definimos un vector de tipo String con cinco elementos:

        Private paises(4) As String

Procedemos a cargar el vector:

        Public Sub Cargar()
            Dim f As Integer
            For f = 0 To 4
                Console.Write("Ingrese el nombre del pais:")
                paises(f) = Console.ReadLine()
            Next
        End Sub

Para el ordenamiento vemos que es idéntico a trabajar con Integer o Single::

        Public Sub Ordenar()
            Dim k, f As Integer
            For k = 0 To 3
                For f = 0 To 3 - k
                    If paises(f) > paises(f + 1) Then
                        Dim aux As String
                        aux = paises(f)
                        paises(f) = paises(f + 1)
                        paises(f + 1) = aux
                    End If
                Next
            Next
        End Sub

Problema propuesto

  1. Cargar un vector de n elementos de tipo entero (n se ingresa por teclado)
    Ordenar posteriormente el vector e imprimirlo
Solución
Module Module1
    Public Class PruebaVector15

        Private vec() As Integer

        Public Sub Cargar()
            Dim cant As Integer
            Console.Write("Cuantos elementos tendrá el vector:")
            cant = Console.ReadLine()
            ReDim vec(cant - 1)
            Dim f As Integer
            For f = 0 To vec.GetUpperBound(0)
                Console.Write("Ingrese elemento:")
                vec(f) = Console.ReadLine()
            Next
        End Sub

        Public Sub Ordenar()
            Dim f, k As Integer
            For k = 0 To vec.GetUpperBound(0) - 1
                For f = 0 To vec.GetUpperBound(0) - 1 - k
                    If vec(f) > vec(f + 1) Then
                        Dim aux As Integer
                        aux = vec(f)
                        vec(f) = vec(f + 1)
                        vec(f + 1) = aux
                    End If
                Next
            Next
        End Sub

        Public Sub Imprimir()
            Console.WriteLine("Vector ordenados de menor a mayor.")
            Dim f As Integer
            For f = 0 To vec.GetUpperBound(0)
                Console.WriteLine(vec(f))
            Next
            Console.ReadKey()
        End Sub
    End Class


    Sub Main()
        Dim pv As New PruebaVector15()
        pv.Cargar()
        pv.Ordenar()
        pv.Imprimir()
    End Sub

End Module

Retornar