Vectores: Ordenamiento por Intercambio

En este post veremos paso a paso cómo ordenar un vector de números de 5 elementos de forma ascendente. Luego generalizaremos la solución a un vector de N elementos.

Planteamiento del Problema

¿Qué tengo?
Un vector de 5 números

¿Qué quiero?
Ordenar el vector de forma ascendente

¿Cómo lo hago?

- Tenemos 5 elementos, de los cuales iremos ordenando posición a posición (empezando por la posición 0)

- Una posición está ordenada cuando todos los elementos de las posiciones posteriores son mayores que el elemento de la posición que se está ordenando.

<imagen de posición i ordenada>

- Si ordenamos posición a posición, vemos que si ordenamos de la posición 0 a la 3, la cuarta quedará ordenada automáticamente (no hay posiciones posteriores con la cual compararla)

Siguiendo estas pautas, haremos el procedimiento para el vector de 5 elementos, razonando a cámara lenta:
(ver enlace)

Ahora que hemos visto poco a poco cómo sería la ejecución del algoritmo, planteamos el pseudocódigo para el vector de 5 elementos:

/***Método de Ordenamiento General***/

iPos = 0; //representa cada posición del vector

Para cada elemento del Vector hasta la posición 3

  OrdenarDesde(iPos); //Ordena el vector a partir de la posición iPos

Fin Para

/***Método OrdenarDesde***/

iPosCompara = iPos + 1; //esta variable es la que recorre las posiciones posteriores a iPos para comparar

elemento1 = Vector[iPos];

Mientras (iPosCompara <= 4)

   elemento2 = Vector[iPosCompara];

   //Se comparan: elemento1 y elemento2

   Si elemento1<= elemento2 //no tiene que cambiar de posición

      iPosCompara++

   Caso Contrario

      Intercambia(iPos, iPosCompara) //intercambia los elementos

      iPosCompara =  iPos + 1; //vuelve a empezar el ordenamiento desde la posición iPos

      elemento1 = Vector[iPos];

   Fin Si

Fin Mientras

/***Método Intercambia***/

aux = Vector[iPos]; //guarda temporalmente el valor de la posición iPos

Vector[iPos] = Vector[iPosCompara];

Vector[iPosCompara] = aux; //utiliza el valor guardado en aux para el intercambio

Para terminar, os dejo el mismo código como un proyecto de consola en c# generalizado para vectores de N elementos.
- Programa Principal
- Clase con Algortimo de Ordenamiento

Sumatorio de valores de un vector

En esta ocasión, trabajaremos con un ejemplo práctico para explicar cómo hacer la sumatoria de valores de un vector.
En este ejemplo tenemos una factura de este estilo:

Descripción	Precio unitario	Cantidad	Total
Boligrafo	1,50	2	3,00
Papel A4 (pack. 100)	4,75	1	4,75
		Total	7,75

Si tenemos una clase que representa cada linea del detalle de la factura, seria de este estilo:

Class Detalle{
  private String descripción;
  private float precioUnitario;
  private int cantidad;
  private float totalLinea;

  //y los respectivos métodos gets y sets para cada atributo
}

Por otra parte tenemos una clase que representa la factura y que tiene varias lineas en el detalle (array de Detalle)

Class Factura{
  private Detalle[100] lineas; //como máximo tiene 100 líneas de detalle
  private int numLineas; //esta variable indica el número de líneas que tiene la factura, siempre <= 100
  private float totalFactura; //esta variable contendrá el total de la factura
}

Desde nuestro programa principal suponemos que la se han cargado los datos de la factura, por tanto tendríamos:

Factura miFactura = new Factura(); //instanciamos el objeto miFactura de tipo Factura
//...
//aquí rellenamos la información en cada linea de detalle
//...
//ahora calculamos el total de la factura
//recorremos todas las lineas de la factura
int numLineasFactura = miFactura.getNumLineas();
float totalCalculoFactura = 0; //inicializamos a 0
for(int i = 0; i < numLineasFactura; i++)
{
   totalCalculoFactura += miFactura.getDetalle()[i].getTotalLinea();
}
//al terminar el for, la variable totalCalculoFactura contiene el total
//guardamos el total en la factura
miFactura.setTotalFactura(totalCalculoFactura);

La clave de este ejemplo está en dos líneas:
1. Sumar el total de cada linea:
    totalCalculoFactura += miFactura.getDetalle()[i].getTotalLinea();

En cada iteración se va incrementando la variable totalCalculoFactura con el valor del total de cada linea. Para acceder al total de cada linea se hace a través de método getDetalle() que retorna el vector de Detalles de la factura, utilizamos el índice i para posicionarnos linea a linea en cada iteración y estando en la linea accedemos al total de la linea mediante el método getTotalLinea().

2. Inicialización de la variable acumuladora:
    float totalCalculoFactura = 0;

La variable totalCalculoFactura es la que va acumulando el total de la suma de cada linea, es muy importante que esté inicializada a 0, debido a que no todos los lenguajes de programación inicializan a 0 cuando se define la variable, es decir, si sólo la definimos y no la inicializamos nada nos garantiza que esa variable contenga el valor 0.

Finalmente, hacemos una variación al problema y suponemos que las lineas de la factura contienen la descripción, el precio unitario, la cantidad pero no tienen calculado el total por linea, en ese caso se podría modificar el programa para realice el cálculo del total en cada línea y a la vez el total de la factura:

int numLineasFactura = miFactura.getNumLineas();
float totalCalculoFactura = 0; //inicializamos a 0
float precioUnitarioLinea;
int cantidadLinea;
for(int i = 0; i < numLineasFactura; i++)
{
   //obtiene el precio unitario y la cantidad por linea
   precioUnitarioLinea = miFactura.getDetalle()[i].getPrecioUnitario();
   cantidadLinea = miFactura.getDetalle()[i].getCantidad();
   //calcula el total de linea y lo guarda en la linea
   miFactura.getDetalle()[i].setTotalLinea(precioUnitarioLinea  * cantidadLinea );
 
   //como el total de linea ya está calculado y guardado se puede utilizar para calcular el total de la factura
   totalCalculoFactura += miFactura.getDetalle()[i].getTotalLinea();
}
//al terminar el for, la variable totalCalculoFactura contiene el total
//guardamos el total en la factura
miFactura.setTotalFactura(totalCalculoFactura);

Búsqueda del valor máximo

Uno de los problemas académicos más comunes es el de la búsqueda del valor máximo o mínimo dentro de una lista. Una aplicación que podríamos darle a este problema sería por ejemplo con fines estadísticos, calcular para una muestra de datos: el máximo, el mínimo y el valor medio.

Antes de plantear el problema vamos a intentar "pensar en cámara lenta" y preguntarnos qué haría nuestra cabeza si tuviésemos que encontrar el valor máximo de una muestra de datos. Suponemos la siguiente muestra de datos:

2, 5, 10, 1, 7

A simple vista diríamos que el máximo es 10, pero ¿Cómo es que lo hemos determinado? si lo vemos en cámara lenta nos daríamos cuenta que:

1. Comparamos el 2 y el 5, como el 5 es mayor, nos quedamos con el 5 y descartamos el 2.
2. Comparamos el 5 con el 10, como el 10 es mayor, nos quedamos con el 10 y descartamos el 5.
3. Comparamos el 10 con el 1, como el 10 es mayor, nos quedamos con el 10 y descartamos el 1.
4. Comparamos el 10 con el 7, como el 10 es mayor, nos quedamos con el 10 y descartamos el 7.

Finalmente el último con el que nos quedamos fue el 10, por tanto, es el 10 el valor máximo.

Si analizamos cada uno de los pasos, vemos que en cada uno de ellos se compara un elemento de la lista con el valor con el que nos hemos quedado en el paso anterior. Si llevamos esto a lenguaje de programación  se puede plantear como un recorrido por todos los elementos de una lista en la que cada iteración realza una comparación entre el valor actual con el máximo de la iteración anterior, por tanto sabemos que debemos tener una estructura así:

//creamos la muestra de datos
int listaNumeros [5]; 
listaNumeros[0] = 2;
listaNumeros[1] = 5;
listaNumeros[2] = 10;
listaNumeros[3] = 1;
listaNumeros[4] = 7;

//tenemos un recorrido de la muestra
for(int i=0; i<5;i++)
{
  //comparamos el valor actual con el resultado de la iteración anterior
  if (listaNumeros[i] > valor_maximo)
  {
    //esta linea representa el "nos quedamos con" de cada paso
    valor_maximo = listaNumeros[i]; 
  }
}

Hasta aquí tenemos la estructura básica del algoritmo, ahora le hacemos algunos ajustes, teniendo en cuenta que la variable valor_maximo no la hemos inicializado.
Si la inicializaramos con 0, nos corremos el riesgo de que para otra muestra tengamos valores negativos y en ese caso el máximo siempre sería 0, lo mejor es tomar como máximo algún valor de la muestra, por ejemplo el primero.

//inicializamos el valor máximo con el primer elemento de la muestra
int valor_maximo = listaNumeros[0];

//tenemos un recorrido de la muestra
for(int i=0; i<5;i++)
{
  //comparamos el valor actual con el resultado de la iteración anterior
  if (listaNumeros[i] > valor_maximo)
  {
    //esta linea representa el "nos quedamos con" de cada paso
    valor_maximo = listaNumeros[i]; 
  }
}

Ahora que nos aseguramos que el valor_maximo de la muestra sea uno de los elementos de la muestra, vemos que la primera iteración comparará listaNumeros[0] y valor_maximo y que siempre serán iguales en la primera iteración, por tanto el código que está dentro del if núnca se ejecutará en la primera iteración, así que podemos aplicar una optimización haciendo que empiece la iteración a partir del segundo elemento, de la siguiente forma.


//inicializamos el valor máximo con el primer elemento de la muestra
int valor_maximo = listaNumeros[0];

//el recorrido se inicia en el segundo elemento
for(int i=1; i<5;i++)
{
  //comparamos el valor actual con el resultado de la iteración anterior
  if (listaNumeros[i] > valor_maximo)
  {
    //esta linea representa el "nos quedamos con" de cada paso
    valor_maximo = listaNumeros[i]; 
  }
}

Finalmente, aprovecharemos el mismo recorrido para calcular el máximo, el mínimo y la media:

//creamos la muestra de datos
int listaNumeros [5]; 
listaNumeros[0] = 2;
listaNumeros[1] = 5;
listaNumeros[2] = 10;
listaNumeros[3] = 1;
listaNumeros[4] = 7;

int valor_maximo = listaNumeros[0];
int valor_minimo = listaNumeros[0];
int media = listaNumeros[0];

for(int i=1; i<5;i++)
{
  //Búsqueda del máximo
  if (listaNumeros[i] > valor_maximo)
  {
    valor_maximo = listaNumeros[i];
  }

  
  //Búsqueda del mínimo
  if (listaNumeros[i] < valor_minimo)
  {
    valor_minimo = listaNumeros[i] ;
  }

  //cálculo de media

  media +=  listaNumeros[i] ;

}

//al terminar el recorrido la variable media contiene la suma de todos los elementos
//dividimos entre el número de elementos para calcular la media
media = media/5;

//En este punto tenemos calculado los tres valores estadísticos de la muestra, los imprimimos en pantalla
printf("valor_maximo: ", valor_maximo);
printf("valor_minimo: ", valor_minimo);
printf("media: ", media);

Búsqueda con recorrido secuencial

Uno de los problemas más frecuentes es el tratamiento de vectores (Array), para esto es necesario tener claros los siguientes conceptos:

- El vector es una lista de elementos, donde todos los elementos son del mismo tipo.

- El vector tiene un número de elementos fijos, cuando se crea, se reserva memoria para todos esos elementos. Por ejemplo, definimos un vector de 15 elementos de tipo unsigned char (1 byte), entonces estaremos reservando 15 bytes en la memoria.

- Es muy importante tener clara la diferencia entre posición y valor. Si el vector tiene N elementos, entonces tendremos posiciones que variarán entre 0 y N-1, y los valores en cada posición dependerán del tipo de elementos del vector.

Para el vector:

int listaNumeros [5]; //vector de 5 elementos de tipo int

Se ha reservado memoria para 5 variables de tipo int, para acceder a los valores de esas variables lo hacemos de la siguiente forma:

listaNumeros[0] = 2; //el valor en la posición 0 es 2

listaNumeros[1] = 5; //el valor en la posición 0 es 5

listaNumeros[2] = 4; //el valor en la posición 0 es 4

listaNumeros[3] = 3; //el valor en la posición 0 es 3

listaNumeros[4] = 1; //el valor en la posición 0 es 1

Se comete mucho el error de acceder a listaNumeros[5], esto dará un error de fuera de rango del vector, porque las posiciones varían entre 0 y 4, por tanto:

listaNumeros[5] = 3; //ERROR!!! no se puede realizar esta asignación porque se encuentra fuera de rango

Para buscar un elemento en un vector que cumpla ciertas características, debemos recorrer uno a uno cada elemento y determinar si el valor en cada posición cumple con las características que estamos buscando. Este recorrido uno a uno de los elementos se le denomina recorrido secuencial.

Por ejemplo, si queremos imprimir por pantalla los números del vector listaNumeros que son pares, haremos:

int N = 5;
for(int i=0; i<N; i++)
{
    //listaNumeros[i] contiene el valor en la posición i
    if(listaNumeros[i] % 2 == 0) //verifica si el valor es par, en ese caso imprime
       printf(listaNumeros[i]);
}

la variable i nos ayuda a recorrer las posiciones del vector (i varía desde 0 hasta N-1).

la variable N representa el número de elementos del vector, notar que las iteraciones del for sólo se ejecutan si i<N
La característica que buscamos es que el valor sea par, para eso utilizamos la operación % que calcula el resto de dividir listaNumeros[i] entre 2, en el caso que sea par ese resto es 0 y en ese caso imprimimos.

Si modificamos el problema y ahora sólo nos interesa mostrar el primer valor par, ¿Qué modificación tendríamos que hacer a programa anterior?

Ahora la característica no es sólo que sea par sino que además sea el primero, por tanto introducimos una variable booleana que nos indique si es el primero en encontrarse o no.

int N = 5;
boolean bPrimerPar = false
for(int i=0; i<N && !bPrimerPar; i++)
{
    //listaNumeros[i] contiene el valor en la posición i
    if(listaNumeros[i] % 2 == 0) //verifica si el valor es par, en ese caso imprime
    {   printf(listaNumeros[i]);
         bPrimerPar = true;
    }
}

Cuando se encuentra el primer valor par, la variable se vuelve true y la validación !bPrimerPar se hace falsa por tanto termina de ejecutar el bucle.

Hemos visto que se pueden realizar búsquedas en las que es necesario recorrer todos los elementos del vector y otras en las que sólo lo recorreremos hasta que encontremos el valor que estamos buscando.

Lo que no debemos olvidar en una iteración

Este post intenta dar las 3 claves principales que no debemos olvidar nunca al realizar iteraciones:

1. Definir e inicializar la variable que itera: Esta variable será la que determine en qué iteración nos encontramos y servirá para terminar la iteración.

2. La condición tope para que termine la iteración: Esta condición evalúa la variable itera y determina si debe continuar iterando o no.

3. La variación de la variable que itera: Esta variación se debe realizar en cada iteración para asegurar que la variable en algún momento cumplirá la condición tope.

Un ejemplo sencillo: Sumar los 10 primeros números enteros positivos:

//variable que acumula la suma
int Suma = 0;
//variable que itera: se inicializa con el primer entero positivo
int i = 1;

//la condición es que la variable iteradora no supere 10, así asegura que se suman los 10 primeros números
while (i <= 10)
{
    suma += i;
    //variación de la variable i, se incrementa en 1
    i++;
}

//cuando salimos del while la variable i vale 11 y la variable suma contiene la suma desde 1 hasta 10

Ahora haremos un ejemplo un poco más complejo, haremos una función que calcule la integral entre 0 y 1 de la función f(x) = x^2

El método que utilizaremos será discretizar la función en incrementos de h = 0.001

float inicio = 0;
float final = 1;
float h = 0.001; //variaciones 
float integral = 0; //en esta variable se guarda el valor calculado de la integral
int it = 0; //esta variable guarda el número de iteraciones que se realicen

float i = inicio; //variable que itera y que se evalúa en la condición tope
//la condición que marca el tope es que no sobrepase el final = 1
while (i <= final)
{
    integral += i * i ; //la evaluación de la función f(x)=x^2 en el punto i es f(i) = i^2 = i*i
    i += h; //incremento de la variable iteradora
    it++;
}
//cuando termina el bucle la variable i contiene un número > a final
//la variable integral contiene la suma de la evaluación de la función en todos los puntos i
//la variable it contiene el número total de iteraciones que se realizaron, que es igual al número de veces que //se evaluó f(i)

//para terminar de calcular la integral se divide entre el número de iteraciones
integral = integral / it;

Las variables booleanas

Nos referimos a variables booleanas a aquellas que utilizamos para indicar que algo es verdadero o falso.

Lo importante de estas variables es que sólo pueden tomar dos valores: verdadero o falso, no hay más posibilidades y esta propiedad la utilizaremos para tomar decisiones, por ejemplo: tengo una variable que se llama bTarifaMenor y que es verdadera si tengo una variable edad de tipo entero <= 12 y en caso contrario será falsa. Podríamos decir que si la variable bTarifa Menor es verdadera aplicaremos un descuento del 20% en el precio de un producto.

La definición de estas variables dependerá del lenguaje de programación que estemos utilizando. No podemos encontrar con los tipos: booblean, bool, Boolean, Bool. En cuanto tengamos claro cual de los tipos es el que utiliza el lenguaje con el que estamos programando definiremos la variable:

Para c# definiríamos así:
bool bTarifaMenor; //definimos la variable booleana
bTarifaMenor = False; //inicializamos la variable con valor falso

int edadCliente = 13; //definimos e inicializamos la variable edad en 13

Para aplicar la lógica de decisión que evalúa el valor de la variable edadCliente utilizamos la instrucción if que sigue la siguiente sintaxis:

if (condición que se evalúa)
{
  //Entre estas llaves va el conjunto de instrucciones que se ejecutan si se cumple
  //la condición que se evalúa
}

aplicando la instrucción de evaluación if en el ejemplo:

//la condición de evaluación es que la edad del cliente sea menor o igual que 12
//dejamos la referencia de los operadores disponibles que iremos aplicando en los ejemplos
if (edadCliente <= 12)
{
  bTarifaMenor = True; //asignamos el valor de verdadero a la variable booleana
}

Las llaves “{“ y “}” contienen un conjunto de instrucciones que sólo se ejecutarán si se cumple la condición que se evalúa dentro del paréntesis, si ese conjunto de instrucciones consta de una sola instrucción como es el caso del ejemplo, se pueden obviar las llaves:

if (edadCliente <= 12)
  bTarifaMenor = True; //asignamos el valor de verdadero a la variable booleana

Sin embargo, si Ud. está empezando a programar le recomiendo que utilice siempre las llaves,  así podrá distinguir claramente cuáles son las instrucciones que se ejecutarán en el caso que se cumpla la condición del if.

Para terminar el ejemplo, aplicaremos el descuento a los menores utilizando como condicional a la variable booleana:

if (bTarifaMenor)
{
 //aquí hace las instrucciones necesarias para aplicar el 20% de descuento en el precio
}

En el caso de este if la condición que se evalúa es simplemente una variable booleana, por que en sí esta variable es True o False, en el caso que su valor sea True se ejecutará el bloque de instrucciones que se encuentra entre las llaves (descuento en el precio).

Aquí más información sobre la instrucción if

Instrucción de Asignación

Ahora que tenemos claro lo que es una variable veremos cómo almacenar información en ellas, para esto utilizamos la instrucción de asignación.

La instrucción de asignación se encarga de guardar un valor en una variable, para esto es importante tener en cuenta que el valor que se guarde debe ser del mismo tipo que se ha definido a la variable, es decir, si defino una variable de tipo entero no podré asignarle un decimal.

La instrucción de asignación tiene la siguiente sintaxis:

nombre variable receptora = valor que se le asigna;

Siempre la variable que recibe el valor va del lado izquierdo al “=”.

Cuando nos referimos a valor que se le asigna puede ser representado de varias formas, que describiremos a continuación:

Asignación de un valor fijo
Se asigna directamente un valor, por ejemplo:
edad = 18;
nombre = “juan”;
precio = 3.5;

Asignación del valor de una variable
Se asigna el valor que contiene otra variable
int edad, edad2; //definimos 2 variables de tipo entero
edad = 18; //inicializamos la variable edad con un valor fijo
edad2 = edad; //inicializamos la variable edad2 con el valor de la variable edad, es decir con 18

Asignación del valor del resultado de una operación
Se asigna el valor del resultado de una operación

Ejemplo con una variable de tipo entero
int edad, edad2; //definimos 2 variables de tipo entero
edad = 18 + 2; //inicializamos la variable edad con el valor resultante de la suma, edad = 20
edad2 = edad - 2; //inicializamos la variable edad2 con el valor de la operación resultante de la resta, edad2 = 18

Ejemplo con una variable de tipo cadena de caracteres
String cadena, cadena2; //definimos 2 variables de tipo cadena de caracteres
cadena = “Juan”;//se incializa con el valor fijo “juan”
cadena2 = cadena + “ “ + “Pérez”; //se inicializa con e valor resultante de la concatencación con “ “ y “Pérez”, queda como resultante “Juan Pérez”

Asignación del valor del resultado de una función
Se asigna el valor del resultado de una función, para esto es necesario que el tipo de dato que retorna la función sea del mismo tipo que el de la variable.

float area, lado; //definimos 2 variable de tipo decimal
lado = 3.5; //inicializamos el la variable lado con la longitud del lado de un cuadrado
area = calcularAreaCuadrado(lado); //invocamos a la función calcularAreaCuadrado que retorna una variable de tipo decimal con el resultado del cálculo del aréa de un cuadrado cuyo lado tiene el valor almacenado en la variable lado