Inserción de valores en un vector ordenado

En esta ocasión trabajaremos una estructura fija (vector) como si fuese una estructura variable, esta solución se puede aplicar en escenarios en los cuales sabemos que:

- Como máximo utilizaremos un número determinado de elementos.
- La inicialización (inserción) se realiza una vez o con muy poca frecuencia,
- Y se necesita acceder continuamente a elementos en concreto.

Por ejemplo, sabemos que en un aula no se puede exceder de los 100 alumnos, la matrícula se realiza al principio de curso y durante el curso se puede acceder en cualquier momento al expediente de cualquiera de los alumnos matriculados.
En un aula podrían inscribirse 25 alumnos y en otra 82 alumnos, si se quisiera imprimir un listado de los alumnos matriculados en cada aula no es necesario recorrer el vector de 100 elementos, sino que en el primero se recorrerá 25 veces y en el segundo 82.

Para hacer uso de los vectores de esta forma utilizaremos una variable auxiliar que representará el número de elementos utilizados, así cada vez que necesitemos hacer una operación sobre todos los elementos no recorreremos todos los elementos del vector sino todos los utilizados.

int listaOrdenada[N];
int numelem = 0; //cantidad de elementos ocupados de la lista

Ahora complicaremos un poco el problema y suponemos que los alumnos cuando se matricula no vienen de forma ordenada, pero se requiere almacenarlos de forma ordenada por apellido, esto implica que cada vez que se agrega un alumno a la lista de matriculados se debe buscar la posición del vector en la cual se debe insertar, no siempre será el último.

Este tipo de problema utiliza varios de los conceptos vistos en entradas anteriores, tales como:

- El uso de vectores para almacenar información del mismo tipo.
- El uso de vectores como estructura que ocupa un espacio de memoria fija de la cuál sólo utilizaremos una parte de forma dinámica.
- El uso de los iteradores for y while para realizar una acción sobre cada elemento de un vector.
- Recorridos de vectores en forma ascendente y en forma descendente
- El uso de comprador if para determinar la posición en la cual se debe insertar el nuevo elemento.

Para simplificar el problema supondremos que los alumnos son números enteros y sus apellidos son números mayores que cero y os invito a que modifiquéis el código para adaptarlo a un vector de una estructura de alumnos que incluya los nombres y los apellidos.

Os dejo el código a continuación en C:

#include <stdio.h>
#include <stdlib.h>
#define N 100


int main(int argc, char *argv[])
{
  //definición de variables
  int listaOrdenada[N];
  int numelem = 0; //cantidad de elementos ocupados de la lista
  int numero;
  int i, j;
  //inicializa vector
  for(i=0; i<N; i++) listaOrdenada[i] = 0;

  //proceso
  //mensajes iniciales
  printf("Ingrese los numeros de la lista \n\nLos numeros deben ser mayores que 0 \nPara introducir pulse <ENTER> \n");
  printf("como maximo puede ingresar %d numeros \n", N);
  printf("Para finalizar pulse 0 y <ENTER>\n");

  //Lee valor a ingresar en el vector
  printf("Numero: ");
  scanf("%d", &numero);
  printf("Numero ingresado %d \n", numero);

  while(numero != 0 && numelem < N)
  {
    i = 0;
    //ubica la posición para insertar el número
    while(i<numelem && listaOrdenada[i] < numero) i++;
    //en el caso que se inserte en la última posición: i == numelem
    if(i==numelem) {
       listaOrdenada[i]=numero;
       numelem++;
    }
    else{
       //tiene que desplazar a todos los elementos posteriores
       j = numelem;
       numelem++;
       //recorre la lista de forma inversa para desplazar los valores
       while(j>i){
         listaOrdenada[j] = listaOrdenada[j-1];
         j--;
       }
       listaOrdenada[i] = numero;
    }
 
    //imprime la lista de elementos 
    for(i=0; i<numelem; i++) printf("%d \t",listaOrdenada[i]);

    printf("\n\nNumero: ");
    scanf("%d", &numero);
    printf("Numero ingresado %d \n", numero);

  }

  printf("Elementos utilizados: %d \n", numelem);

  system("PAUSE");
  return 0;
}