Hola en esta ocacion les voy a compartir un ejercicio sobre algoritmos de ordenación pero con registros , donde se pedirá que ordene un registro segun nombre, segun apellido, segun código.
Introduccion:
Cuando estudiamos los algoritmos de ordenamiento,
siempre por lo general nos referimos a números, pero en la vida real no solo
necesitamos ordenar números, sino también palabras, como nombres, apellidos,
etc. El orden de este tipo de datos es distinto al de los números pues aquí
tomamos como referencia un orden alfabético, empezando por la letra “a” y
terminando en “z”, En este informe
detallaremos más acerca de cómo ordenar no solamente números sino también
palabras, y específicamente nos referimos a las estructuras de datos compuestas
como los registros. Los registros son un tipo de dato compuesto pues pueden
contener valores numéricos como también caracteres. En este caso en específico
utilizaremos el Algoritmo de Burbuja, en dos formas uno para enteros y otros
para caracteres.
Algoritmo:
Como se mencionó en la introducción en este trabajo
utilizaremos el Algoritmo Burbuja, este es un sencillo algoritmo de
ordenamiento en el
cual su funcionamiento consta en revisar cada elemento de la lista que va a ser
ordenada con el siguiente, intercambiándolos de posición si están en el orden
equivocado. Es necesario revisar varias veces toda la lista hasta que no se
necesiten más intercambios, lo cual significa que la lista está ordenada. Para
la ordenación de registros modificaremos el algoritmo para poder ordenar
estructuras.
- Para números enteros:
void ordenacion_burbuja(int n)
{
int i,j, bandera;
for(i=1; i<n; i++) {
bandera=0; //inciamos la
bandera en 0
for(j=n-1; j>=i; j--) {
if(alumno[j-1].codigo>alumno[j].codigo) {
aux=alumno[j];
alumno[j]=alumno[j-1];
alumno[j-1]=aux;
bandera=1; //si hubo cambio cambiamos la bandera a 1
}
}
if (bandera==0)
break; //si no
hubo cambios entonces salir del for
}
}
- Para cadenas:
void ordenacion_burbuja_nombre(int n)
{
int i,j, bandera;
int temp;
for(i=1; i<n; i++)
{
bandera=0; //inciamos la bandera en 0
for(j=n-1; j>=i; j--)
{
temp=strcmp(alumno[j-1].nombres,alumno[j].nombres);
if(temp>0)
{
aux=alumno[j];
alumno[j]=alumno[j-1];
alumno[j-1]=aux;
bandera=1; //si hubo cambio
cambiamos la bandera a 1
}
}
if (bandera==0)
break; //si no hubo cambios entonces
salir del for
}
}
Ejemplos:
Para mostrar algún ejemplo debemos tener una estructura:
N°
|
Código
|
Nombres
|
Apellidos
|
1
|
456789
|
Joel
|
Fernández segura
|
2
|
123456
|
Edinson
|
Saldaña Ramos
|
A continuación se mostraran 2 ejemplos en los cuales se ingresaran
datos de 2 personas y se hará la comparación con el algoritmo Burbuja:
Nombre
J
|
O
|
E
|
L
|
|||
E
|
D
|
I
|
N
|
S
|
O
|
N
|
En este caso se a ingresado 2 nombres distintos y la comparación se
ara letra por letra y el resultado que dará es:
Posición
0: EDINSON
Posición
1: JOEL
Luego de mostrar
que el nombre Edinson es mayor, ocurrirá un intercambio de posición de
registros, entonces cambiaran la estructura [0] por la estructura [1] y
viceversa. Para lo cual nuestro algoritmo terminaría de ordenar los registros
de acuerdo al nombre.
Supongamos
que tengamos el siguiente caso:
M
|
A
|
R
|
I
|
A
|
||
M
|
A
|
R
|
I
|
T
|
A
|
En este caso
como vemos que llegamos a tener 4 letras iguales por lo que el algoritmo se encargara
de hacer la comparación uno por uno hasta que llegue a encontrar alguna
diferencia y el resultado será el siguiente:
Posición 0: MARIA
Posición
1: MARITA
Por
lo tanto en este caso no habrá cambio de posición en los registros.
Lo mismo se hará
al momento de ingresar apellido y código, el algoritmo se encargara de hacer
todas las comparaciones posibles y mostrar el resultado de acuerdo a lo
solicitado.
Análisis Tiempo de Ejecucion - Complejidad:
Como
podemos ver el análisis del algoritmo de burbuja para los dos casos uno que
ordena enteros y otro que ordena cadenas es el mismo, no hay cambios por la
modificación de líneas ya que en el segundo algoritmo se usó una comparación
strcmp de la librería String.h, pero esta línea sigue teniendo una complejidad
O(1).
Implementacion en C++:
Espero te sea de ayuda si deseas el codigo completo puedes obtenerlo aqui
SOCIALIZA ESTO →