Subconjunto ordenado de array

El siguiente ejemplo pide ingresar una lista de números positivos y guardarlos en un array, para luego leerlos y copiar a otro array de forma ordenada sólo aquellos que son múltiplos de 5.

Un ejemplo de ejecución:

¿Qué cambiarías en el programa para que extraiga los múltiplos de otro número?

¿Qué cambiarías para que el orden sea ascendente?

¿Qué otras variaciones añadirías al programa?

#include <iostream>

int main(int argc, char** argv) {

int fin = 0;

int numero;

int listaNumeros[20];

int totalNumeros = 0;

int listaOrdenada[20];

int totalOrdenada = 0;

//lectura por teclado de un conjunto de números positivos, como máximo 20 números

while(!fin && totalNumeros<20){

printf("ingrese un numero:");

scanf("%d", &numero);

if(numero > 0) {

listaNumeros[totalNumeros] = numero;

totalNumeros++;

}else{

fin++;

}

}

//imprimir la lista

for(int i = 0; i<totalNumeros; i++) printf("%d ", listaNumeros[i]);

//seleccionar los múltiplos de 5 ordenados descendente

for(int i = 0; i<totalNumeros; i++){

if( (listaNumeros[i]%5) == 0 ){

int encuentra = 0;

int indice; //indice que recorre la lista ordenada para encontrar la posición donde insertar

int multiploInsertar = listaNumeros[i];//número a insertar en la lista ordenada

indice = totalOrdenada - 1;

//recorremos la lista ordenada de forma descendente y vamos desplazando hasta qu encontramos la posición correcta

while(!encuentra && indice >= 0){

//comparo el número a ubicar con el elemento en la ListaOrdenada en la posición índice

if(multiploInsertar > listaOrdenada[indice]){

//como es mayor muevo el valor de lista ordenada al siguiente índice

listaOrdenada[indice + 1 ] = listaOrdenada[indice];

}

else{

listaOrdenada[indice+1] = multiploInsertar;

totalOrdenada++;

encuentra = 1;

}

indice--;

}

if(!encuentra) {//en el caso que recorra todo el arrayOrdenado y sea mayor a todos, se coloca en el primer elemento

listaOrdenada[0] = multiploInsertar;

totalOrdenada++;

}

}

}

//imprimir la lista

printf("\nNumero de multiplos encontrados %d\n", totalOrdenada);

for(int i = 0; i<totalOrdenada; i++) printf("%d ", listaOrdenada[i]);

return 0;

}

Ordenamiento de una lista simplemente enlazada

El ordenamiento de una lista simplemente enlazada es similar al ordenamiento de vectores con la gran diferencia de que en una lista simplemente enlazada no disponemos del concepto del “índice” que nos ayuda a acceder directamente a un elemento de la lista, en este caso para acceder a un elemento debemos recorrer desde el inicio hasta hallar el elemento que nos interese.

Un algoritmo sencillo es el del Intercambio, consiste en lo siguiente:

1. Situar un puntero al inicio de la lista que nos irá indicando a medida que vayamos ordenando, cuánto de la lista ya está ordenada, es la variable más importante del algoritmo porque nos servirá para saber que hemos acabado de ordenar la lista.

Elemento * elemBase = elemInicio;

while(elemBase != NULL)

{

//en este proceso vamos ordenando la lista a partir del nodo elemBase hasta el final

elemBase = elemBase->next;

}

2. En el caso que el ordenamiento sea de menor a mayor, necesitamos encontrar el menor de los elementos a partir del elemento base hasta el final de la lista.

En el caso del ordenamiento de Vectores obteníamos la posición, en este caso obtendremos un puntero al menor elemento.

Elemento* buscarMenor(Elemento* ptrInicial)

Esta función tendría que utilizarse en cada iteración

Elemento * elemBase = elemInicio;

Elemento* elemMenor; //puntero que nos sirve para apuntar al menor elemento encontrado

while(elemBase != NULL)

{

elemMenor = buscarMenor(elemBase);

elemBase = elemBase->next;

}

3. Intercambiar el elemento menor con el elemento que se encuentra apuntando el puntero base. Para hacer este intercambio es necesario que el elemento anterior al elemento base apunte al elemento menor, para eso necesitamos un puntero que apunte al anterior del elemento base.

Como es una lista simplemente enlazada, no podemos retroceder para hallar al puntero anterior al puntero base, por tanto, crearemos una función que nos sirva para ubicarnos en el elemento anterior que queramos. Esta función es necesaria para luego poder hacer el intercambio de nodos.

Elemento * getElemAnterior(Elemento* elemInicio, Elemento* elem);

Utilizaremos esta función para obtener el elemento anterior al base y al menor y de esta forma poder realizar el intercambio

Elemento * elemAnteBase = NULL;//puntero que apunta al anterior de elemento base

Elemento * elemBase = elemInicio;

Elemento* elemAnteMenor; //puntero que apunta al anterior del elemento menor

Elemento* elemMenor; //puntero que nos sirve para apuntar al menor elemento encontrado

while(elemBase != NULL)

{

elemMenor = buscarMenor(elemBase);

elemAnteBase = getElemAnterior(elemInicio, elemBase);

elemAnteMenor = getElemAnterior(elemInicio, elemMenor);

elemBase = elemBase->next;

}

Teniendo el puntero anterior al base ya podemos hacer el intercambio:

void intercambio(Elemento* elemAnteBase, Elemento* elemBase,

Elemento* elemAnteMenor, Elemento* elemMenor);

Incorporamos el intercambio en cada iteración y asignamos el nodo menor como el nuevo elemento base:

Elemento * elemAnteBase = NULL;//puntero que apunta al anterior de elemento base

Elemento * elemBase = elemInicio;

Elemento* elemAnteMenor; //puntero que apunta al anterior del elemento menor

Elemento* elemMenor; //puntero que nos sirve para apuntar al menor elemento encontrado

while(elemBase != NULL)

{

elemMenor = buscarMenor(elemBase);

elemAnteBase = getElemAnterior(elemInicio, elemBase);

elemAnteMenor = getElemAnterior(elemInicio, elemMenor);

intercambio(elemAnteBase, elemBase, elemAnteMenor, elemMenor);

elemBase = elemMenor;

elemBase = elemBase->next;

}

4. Finalmente desarrollamos las funciones:

Elemento* buscarMenor(Elemento* ptrInicial)

{

Elemento* elemMenor = ptrInicial;

Elemento* ptr = ptrInicial;//puntero que sirve para recorrer la lista

int menorValor = elemMenor.valor;//inicializamos el primer valor menor

//recorremos toda la lista y dejamos el puntero elemMenor en el de menor valor

while(ptr!=NULL)

{

if(ptr.valor < menorValor)

{

elemMenor = ptr;

menorValor = ptr.valor;

}

ptr = ptr->next;

}

return elemMenor;

}

void intercambio(Elemento* elemAnteBase, Elemento* elemBase,

Elemento* elemAnteMenor, Elemento* elemMenor)

{

Elemento* aux = elemBase->next; //nos sirve para hacer el intercambio sin perder punteros

elemBase->next = elemMenor->next;

elemMenor->next = aux;

elemAnteBase->next = elemMenor;

elemAnteMenor->next = elemBase;

}

Elemento * getElemAnterior(Elemento* elemInicio, Elemento* elem)

{

Elemento*anterior = NULL;

Elemento*ptr = elemInicio;

int finBusqueda = 0;

while(ptr!=NULL && ptr->next!=NULL && !finBusqueda)

{

if(ptr->next.valor == elem.valor)

{

finBusqueda = 1;

}

anterior = ptr;

ptr = ptr->next;

}

return anterior;

}

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;
}

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