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 int, float como cadena de caracteres. 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.
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.
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
¿Porque 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: (f=0 ; f<4-k; f++)
Es decir restarle el valor del contador del for externo.
Programa:
#include<iostream>
using namespace std;
class OrdenamientoSueldos {
private:
int sueldos[5];
public:
void cargar();
void ordenar();
void imprimir();
};
void OrdenamientoSueldos::cargar()
{
for(int f=0;f < 5;f++)
{
cout <<"Ingrese el sueldo:";
cin >>sueldos[f];
}
}
void OrdenamientoSueldos::ordenar()
{
for (int k = 0; k < 4; k++)
{
for (int f = 0; f < 4 - k; f++)
{
if (sueldos[f] > sueldos[f + 1])
{
int aux;
aux = sueldos[f];
sueldos[f] = sueldos[f + 1];
sueldos[f + 1] = aux;
}
}
}
}
void OrdenamientoSueldos::imprimir()
{
cout <<"Sueldos ordenados de menor a mayor.";
cout <<"\n";
for(int f=0;f < 5;f++)
{
cout <<sueldos[f];
cout <<"\n";
}
cin.get();
cin.get();
}
int main()
{
OrdenamientoSueldos os;
os.cargar();
os.ordenar();
os.imprimir();
return 0;
}
Este proyecto lo puede descargar en un zip desde este enlace : VectorOrdenamiento1.zip
También podemos ordenar vectores cuyas componentes sean cadenas de caracteres. Para esto no podemos utilizar el operador > sino debemos utilizar la función strcmp:
char cad1[40]="juan";
char cad2[40]="analia";
if (strcmp(cad1,cad2)>0)
{
cout <<cad1;
cout <<" es mayor alfabéticamente que ";
cout <<cad2;
}
La función strcmp retorna un valor mayor a cero si cad1 es mayor alfabéticamente. En este ejemplo cad1 tiene un valor alfabéticamente mayor a cad2, luego strcmp retorna un valor mayor a cero.
Si las dos cadenas son exactamente iguales la función retorna un cero, y finalmente si cad1 es menor alfabéticamente retorna un valor menor a cero.
Problema 2:
Definir un vector donde almacenar los nombres de 5 paises. Confeccionar el algoritmo de ordenamiento alfabético.
Programa:
#include<iostream>
using namespace std;
class OrdenamientoPaises{
private:
char paises[5][40];
public:
void cargar();
void ordenar();
void imprimir();
};
void OrdenamientoPaises::cargar()
{
for(int f=0;f < 5;f++)
{
cout <<"Ingrese el nombre del pais:";
cin.getline(paises[f],40);;
}
}
void OrdenamientoPaises::ordenar()
{
for (int k = 0; k < 4; k++)
{
for (int f = 0; f < 4 - k; f++)
{
if (strcmp(paises[f],paises[f + 1])>0)
{
char aux[40];
strcpy_s(aux, 40, paises[f]);
strcpy_s(paises[f],40, paises[f + 1]);
strcpy_s(paises[f + 1],40, aux);
}
}
}
}
void OrdenamientoPaises::imprimir()
{
cout <<"Paises ordenados en forma alfabética:";
cout <<"\n";
for(int f=0;f < 5;f++)
{
cout <<paises[f];
cout <<"\n";
}
cin.get();
}
int main()
{
OrdenamientoPaises op;
op.cargar();
op.ordenar();
op.imprimir();
return 0;
}
Definimos el vector para almacenar los 5 países de hasta 39 caracteres:
private:
char paises[5][40];
Procedemos a cargar el vector:
void OrdenamientoPaises::cargar()
{
for(int f=0;f < 5;f++)
{
cout <<"Ingrese el nombre del pais:";
cin.getline(paises[f],40);;
}
}
Para el ordenamiento utilizamos la función strcmp para verificar si tenemos que intercambiar las componentes:
if (strcmp(paises[f],paises[f + 1])>0)
En el caso que si tenemos que intercambiarla utilizamos un auxiliar y mediante la función strcpy_s procedemos a copiar las cadenas de una variable a otra (no se puede utilizar el operador =), el segundo parámetro indicamos la cantidad de caracteres a copiar de una cadena a otra:
char aux[40];
strcpy_s(aux, 40, paises[f]);
strcpy_s(paises[f],40, paises[f + 1]);
strcpy_s(paises[f + 1],40, aux);
Este proyecto lo puede descargar en un zip desde este enlace : VectorOrdenamiento2
Problema propuesto
- Cargar un vector de 5 elementos enteros. Ordenarlo de mayor a menor y mostrarlo por pantalla, luego ordenar de menor a mayor e imprimir nuevamente.
#include<iostream>
using namespace std;
class OrdenamientoVector {
private:
int vec[5];
public:
void cargar();
void ordenarMayorMenor();
void ordenarMenorMayor();
void imprimir();
};
void OrdenamientoVector::cargar()
{
for (int f = 0; f < 5; f++)
{
cout << "Ingrese valor:";
cin >> vec[f];
}
}
void OrdenamientoVector::ordenarMayorMenor()
{
for (int k = 0; k < 4; k++)
{
for (int f = 0; f < 4 - k; f++)
{
if (vec[f] < vec[f + 1])
{
int aux;
aux = vec[f];
vec[f] = vec[f + 1];
vec[f + 1] = aux;
}
}
}
}
void OrdenamientoVector::ordenarMenorMayor()
{
for (int k = 0; k < 4; k++)
{
for (int f = 0; f < 4 - k; f++)
{
if (vec[f] > vec[f + 1])
{
int aux;
aux = vec[f];
vec[f] = vec[f + 1];
vec[f + 1] = aux;
}
}
}
}
void OrdenamientoVector::imprimir()
{
for (int f = 0; f < 5; f++)
{
cout << vec[f];
cout << "-";
}
cout << "\n";
}
int main()
{
OrdenamientoVector ov1;
ov1.cargar();
ov1.ordenarMenorMayor();
ov1.imprimir();
ov1.ordenarMayorMenor();
ov1.imprimir();
return 0;
}
Este proyecto lo puede descargar en un zip desde este enlace :OrdenamientoVector