3.1 Vectores

Hasta ahora, vimos variables que pueden guardar un único valor. Vamos a empezar a ver ahora, variables que pueden guardar varios valores simultáneamente. La primera estructura de este tipo que vamos a ver, son los vectores.

Un vector es una serie de variables del mismo tipo que ocupan lugares consecutivos en la memoria. Por ejemplo, la declaración

        int v[10];

define un vector llamado v que guardará 10 valores enteros. Para acceder a cada uno de ellos individualmente, se coloca el número de posición entre los corchetes, empezando de cero. Así, el primero elemento del vector será v[0], el segundo v[1], etcétera hasta el décimo elemento que será v[9].


Por ejemplo, la instrucción.

     v[6] = v[3] + v[4];

toma el cuarto elemento del vector (v[3]) y el quinto elemento (v[4]), suma sus valores y guarda el resultado en el séptimo elemento (v[6]).

El siguiente programa, pide al usuario que ingrese una cantidad de elementos y calcula el promedio.



#define T 10
#include <iostream>
using namespace std;

int main()
{
       int lista[T];
       int i, cant, suma;
       double prom;
       do
       {
             cout << "ingrese cantidad de elementos: ";
           cin >> cant;
       }
       while (cant < 1 || cant >T);

       for (i=0; i<cant; i++)
       {
             cout << "Ingrese un elemento: ";
             cin >> lista[i];
       }
       suma = 0;
       for (i=0; i<cant; i++)
       {
             suma += lista[i];
       }
       prom = (double) suma/cant;
       cout << "El promedio es " << prom <<endl;
                          
       system ("pause");
       return 0;
}


El espacio de memoria que ocupará el vector se reserva antes de ejecutar el programa, por lo que la cantidad de elementos que tendrá el vector no puede ser una variable cuyo valor se defina durante la ejecución del programa. En este ejemplo, definimos una constante (o "macro") llamada T que eequivale a 10, con la directiva al preprocesador #define. Antes de compilar el programa, el preprocesador lee la instrucción #define y reemplaza todas las apariciones de T con el valor 10. Si más tarde se desea cambiar el tamaño del vector, aún se debe acceder al código fuente y modificar el valor de T a mano, pero este cambio es uno solo y en las primeras líneas del programa, lo que va a evitar errores producidos al olvidar cambiar el tamaño del vector en alguna instrucción.

Para que el usuario decida la cantidad de elementos del vector que quiere utilizar, le pedimos que ingrese dicho valor en la variable cant. La validación de dicha variable hecha con el ciclo do...while impide que el usuario elija un valor mayor a 10.
Es muy importante asegurarse de que el programa no intentará utilizar más elementos de los que el vector tiene definidos (posiciones 10, 11, 12, etc. de nuestro ejemplo): El C++ no realiza esta verificación y asignar dichos valores producirá errores imprevisibles.
Una vez que el usuario definió la cantidad de elementos que va a usar, utilizaremos siempre esa cantidad, sin importarnos más el tamaño real del vector.
Luego, en un primer ciclo, se le pide al usuario que ingrese cant valores, que serán guardados en las primeras cant posiciones del vector (desde lista[0] hasta lista[cant-1]). En cada iteración del ciclo, i toma un valor diferente, por lo que el valor ingresado en el cin se guarda en una posición diferente del vector.
El segundo ciclo acumula todos los números en la variable suma. No es necesario un contador para calcular el promedio, ya que la variable cant indica la cantidad de valores.

3.2 Ordenamiento de vectores

Si tenemos un vector con una serie de datos cargados, es posible que querramos tener esos datos ordenados (de menor a mayor, o de mayor a menor).
Para ordenar un vector se quieren poner los elementos mayores en el final de dicho vector, y los elementos menores al principio. Para ello, sólo contamos con la instrucción if.
Lo que haremos es comparar el primer elemento con todos los que lo siguen. Si alguno de los que lo siguen es menor, intercambiamos sus posiciones.


Comparamos el primer elemento (15) con el segundo (7). Como 15 es mayor, los intercambio. Ahora comparo el primero (7) con el tercero (12). Como no es mayor, no los intercambio. Comparo 7 con 9 y tampoco los intercambio. Finalmente, comparo el primero (7) con el quinto (3). Como el primero es mayor, los intercambio. Luego de comparar el primer elemento con todos los que le siguen, podemos asegurar que el primer elemento es el menor de todos.

Ahora repetimos el procedimiento comparando el segundo elemento con todos los que le siguen.

 Comparo 15 con 12. Como es mayor, los intercambio. Luego comparo 12 con 9 y como es mayor, también los intercambio. Por último, comparo 9 con 7 y también los intercambio. Ahora puedo asegurar que el primer y el segundo elemento están ordenados.

En la siguiente vuelta, comparamos el tercer elemento con todos los que siguen:

Comparo el tercero (15) con el cuarto (12) y los intercambio. Luego comparo 12 con 9 y los intercambio. Ahora puedo asegurar que los tres primeros elementos del vector están ordenados.

Ahora comparo el cuarto elemento con todos los que siguen:


Comparo 15 con 12 y los intercambio. Puedo asegurar que el cuarto también está ordenado. Como todos los elementos menos el último están ordenados; el último elemento es el mayor de todos y tambien está ordenado, no tengo que continuar.

Vamos a ver ahora el programa que implementa este algoritmo:



#include <iostream>
using namespace std;

#define TAM 5

void main()
{
       int v[TAM];
       int i,j, aux;
       // Cargo el vector
       for (i=0; i<TAM; i++)
             v[i] = rand()%100;

       for (i=0; i<TAM; i++)
             cout << v[i] << " ";
       cout << endl;

       // Ordenamiento

       for (i=0; i<TAM-1; i++)    // i va desde el primer elemento al penúltimo
             for (j=i+1; j<TAM; j++)    //j va desde el siguiente (i+1) hasta el final
                    if (v[i]>v[j])          // Si el primero es mayor...
                    {
                           aux  = v[i];        //  .... los intercambio
                           v[i] = v[j];
                           v[j] = aux;
                    }

 for (i=0; i<TAM; i++)
             cout << v[i] << " ";
       cout << endl;
      
}


 Si en lugar de ascendente, quiero hacer un ordenamiento descendente, sólo tengo que cambiar el signo > por < en la comparación.
Este método de ordenamiento se llama ordenamiento por burbujeo, ya que (con mucha imaginación), los elementos más "livianos" suben rápidamente como burbujas en el agua, mientras que los más pesados se van hundiendo lentamente.

3.3 Búsqueda de elementos en un vector

Uno de los usos principales para los vectores es que permiten guardar mucha información, para poder acceder luego a la misma. Este acceso puede ser general (quiero acceder a todos los elementos de un vector) o específico (quiero acceder a un dato en particular).
En el primer caso, sólo hay que recorrer el vector entero con ciclo. Vamos a ver ahora cómo acceder a un dato específico en un vector, mediante algoritmos de búsqueda.
Para ello, vamos a crear una función Buscar, que deberá recorrer el vector viendo si cada elemento del mismo coincide con el dato a buscar. Si el elemento coincide, la función debe devolver la posición del vector en la que está, si no coincide debe pasar a comparar el siguiente elemento. Si llego al final del vector sin haber encontrado un elemento igual al dato, significa que no hay un elemento igual en el vector. En este caso, la función deberá devolver -1 para que el programa sepa que no se encontró el dato. 



int buscar(long v[], int tam, long elem)
{
       int i;
       for (i=0; i<tam; i++)
       {
             if(v[i]== elem) return i; // Si un elemento coincide, devuelve la posición.
       }
       // si llegó hasta acá, significa que terminó el ciclo sin encontrarlo
       return -1;
}


La función recibe como parámetros el vector, un int con la cantidad de elementos que tiene el vector y el dato a buscar, que es del mismo tipo de dato que el vector. Devuelve un int con la posición en que encontró el dato (o -1 si no lo encuentra).

Un programa que use la función, podría ser por ejemplo:




#include <iostream>
using namespace std;

#define T 10

int buscar (long [], int, long );

void main()
{
       long Padrones[T];
       int i,pos;
       long pad;

       // Cargo el vector
       for (i = 0; i<T;i++)
       {
             cout <<" Ingrese un padron:";
             cin >> Padrones[i];
       }

       cout << "Vector cargado."<<endl<<endl;
       cout << "Ingrese el padrón que desea buscar:";
       cin >> pad;

       pos = buscar (Padrones, T, pad);

       if (pos != -1)
             cout <<"El elemento se encuentra en la posición "<< pos <<endl;
       else
             cout <<"El elemento no se encuentra en el vector"<<endl;

       cin >> i;
}


Primero se carga el vector. Luego se le pide al usuario que ingrese un número de padrón, y se llama a la función buscar, pasándole ese número de padrón.
Si el valor que devuelve la función es -1, significa que el elemento no estaba en el vector, en caso contrario, devuelve la posición en la que está el padrón.

Este método de búsqueda, no es muy eficiente, si el elemento no está en el vector, tiene que comparar todos los elementos del vector para darse cuenta. Si el elemento está en el vector, depende de su posición: si el el primero, lo encuentra en una comparación; pero si el elemento es el último, tardará N comparaciones en encontrarlo. Si N es la cantidad de elementos del vector, se tardará en promedio N/2 comparaciones en encontrar el elemento.

Si queremos hacer la búsqueda más rápidamente, necesitamos que el vector esté ordenado. Así, en vez de empezar a comparar desde el principio, comparamos el dato con el elemento que está en la mitad del vector. Si el dato es menor al elemento medio del vector, ya podemos descartar toda la mitad superior del mismo. Si el elemento es mayor, descartamos la primera mitad del vector. Luego podemos llamar recursivamente a la función para que busque en el medio vector que le queda.
Así hasta que el elemento medio del vector sea igual al dato, o hasta que no quede sub-vector donde buscarlo. Esta búsqueda es mucho más rápida, ya que cada comparación permite descartar la mitad de los elementos del vector. Se puede comprobar que la cantidad de búsquedas a realizar es aproximadamente log2(n) / 2, lo que es mucho más rápido que n/2, y esa diferencia aumenta más cuanto más grande sea n.




int buscar_binario(long v[], int desde, int hasta, long elem)
{
       int mitad;
       if (desde > hasta)
             return -1;              // me quedé sin vector donde buscar!!
       mitad = (desde+hasta) /2;
       if (v[mitad] == elem)       //Lo encontré
                return mitad;
       else
             if (v[mitad]< elem)     //Debo buscar en la segunda parte del vector, entre mitad+1 y hasta
                    return buscar_binario(v,mitad+1,hasta,elem);
             else                    //Debo buscar en la primera parte, entre desde y mitad-1
                    return buscar_binario(v,desde,mitad-1,elem);
}



La función tiene cuatro salidas posibles:
 - Si los límites "desde" y "hasta" están cruzados (desde > hasta) significa que fui achicando el rango en el que buscar tanto que ya no me quedó vector donde buscar. Por lo tanto, el dato a buscar no está en el vector y devuelvo -1.
- Si el dato a buscar coincide con el elemento que está en la mitad del rango en el que busco, devuelvo la posición de esa mitad y termina la búsqueda.
- Si el dato a buscar es mayor que el elemento que está en la mitad del vector, debo buscar en el rango (mitad+1; hasta) del vector.
- Si el dato a buscar es menor que el elemento que está en la mitad del vector, debo buscar en el rango (desde; mitad-1) del vector.

El programa que llama a la función podría ser similar al anterior, sólo habría que asegurarse de ordenar el vector antes de llamar a la función, y modificar la llamada para que quede:



pos = buscar_binario (Padrones, 0, T-1, pad);  //Desde = 0;  Hasta = T-1