Programación en C++ / Principios y Aplicaciones (resumen)
Carlos Romero Shollande
1. Introducción
Con frecuencia el programador trabajará con grandes cantidades de información almacenada en arreglos.
Muchas veces, se requiere ordenar dicha información y buscar sí un valor especificado está contenido en algún arreglo.
El ordenamiento, la búsqueda y la mezcla de datos son problemas que estudiaremos en la presente sesión.
2. Ordenamiento
El ordenamiento de datos (sort en inglés) consiste en colocar los datos en algún orden particular (por ejemplo; ascendente o descendente).
Es una de las tareas que consume más tiempo; por este motivo, se han desarrollado cientos de métodos diferentes para la ordenación de datos, y es imposible determinar cuál es el mejor en todas las circunstancias.
Los métodos de ordenamiento más usados son:
- Método de la burbuja, es el método más común, pero tiene pocas características positivas y es mejor no utilizarlo.
- Método de selección
- Método de inserción, son útiles para arreglos pequeños.
- Método de Shell, es el método que más se utiliza, incluso para arreglos con miles de entradas.
2.1. Ordenamiento por Burbuja
A este método también se le conoce como “Ordenamiento por Hundimiento”.
Los valores más pequeños gradualmente burbujean hacia la parte alta del arreglo, como las burbujas de aire que ascienden en el agua, mientras que los valores más grandes se hunden al fondo del arreglo.
La técnica consiste en pasar varias veces por el arreglo. En cada paso, se comparan pares sucesivos de elementos. Por ejemplo, si se desea ordenar los valores del arreglo:
X[i] = [6 8 5 3]
en orden ascendente, existen dos procedimientos:
Método 1
1) Se definen dos subíndices (i y j), el primero para definir el número de pase por el arreglo y el segundo para las comparaciones.
2) Aunque hay (n=4) elementos en el arreglo, solo se efectúan (n-1=3) comparaciones en cada pase. Así mismo, sólo se necesitan (n-1=3) pases por el arreglo, por lo tanto los rangos de cada subíndice son:
i : 1 .. n-1
j : 1 .. n-1
Por lo tanto, los bucles a utilizar son los siguientes:
Para i=1 Hasta n-1 Variación 1
Para j=1 Hasta n-1 Variación 1
3) Se realiza una comparación entre ambos elementos del par sucesivo de elementos.
Si X[j]>X[j+1] Entonces
Primero se compara X[1] con X[2], luego X[2] con X[3] y X[3] con X[4].
Si uno de los pares está en orden descendente, se intercambian sus valores en el arreglo.
Si el par está en orden ascendente (o son idénticos los valores), se quedan tal como están.
4) En el caso de que se requiera de un intercambio y con la finalidad de garantizar la conservación de los valores del arreglo, se utiliza una variable auxiliar (t) sobre la cual se copiara el valor del primer elementos del par (X[j]). Por ejemplo:
Gráfica 1. Pase del primer elemento a la variable auxiliar.
Gráfica 1. Pase del primer elemento a la variable auxiliar.
Es decir: t = X[j]
Enseguida se hace una copia del valor del segundo elemento del par (X[j+1]) sobre el primer elemento (X[j]):
Gráfica 2. Pase del segundo elemento al primer elemento.
Es decir: X[j] = X[j+1]
Luego se hace una copia del valor de la variable auxiliar (t) sobre el segundo elemento (X[j+1]):
Gráfica 3. Pase de la variable auxiliar al segundo elemento.
Es decir: X[j+1] = t
Finalmente, los elementos quedarán ordenados de la siguiente manera:
Gráfica 4. Ubicación definitiva del ordenamiento
En el primer pase, se garantiza que el mayor valor se hunde hasta el fondo del arreglo.
En el segundo pase se garantiza que el segundo valor mayor se hunde hasta la penúltima posición y así sucesivamente.
Método 2
1) Este método consiste en comparar todos los elementos del arreglo en pares de elementos, para ello se definen dos subíndices, i para definir al primer elemento del par y j para el segundo elemento.
2) Se determina el rango de cada subíndice, teniendo en cuenta que para realizar las comparaciones, el primer elemento del par X[i], comenzará en la posición 1 y el segundo se iniciará en una posición más adelante que el primero X[j]=X[i+1].
El primero terminará en una posición menor que el último X[n-1] y el segundo en la última posición X[n]. En el ejemplo las comparaciones serían:
Grafica 5. Determinación de los rangos de cada subíndice.
Grafica 5. Determinación de los rangos de cada subíndice.
Por lo tanto, los rangos de cada subíndice estarán definidos por:
i: 1 .. n-1
j: i+1 .. n
Luego, los bucles a utilizar son los siguientes:
Para i=1 Hasta n-1 Variación 1
Para j=i+1 Hasta n Variación 1
3) Se realiza la comparación entre los elementos de cada par, mediante la siguiente condición:
Si X[i]>X[j] Entonces
En la primera iteración del bucle i se compara X[1] con X[2], luego con X[3] y finalmente con X[4].
Si uno de los pares está en orden descendente, se intercambian sus valores en el arreglo.
Si el par está en orden ascendente (o son idénticos los valores), se quedan tal como están.
4) En el caso de que se requiera de un intercambio y con la finalidad de garantizar la conservación de los valores del arreglo, se utiliza un procedimiento similar al del método 1 de ordenamiento por burbuja. Por ejemplo, la comparación del segundo elemento con el tercero: Primero se copia el valor del primer elemento del par X[i] sobre la variable auxiliar (t):
Gráfica 6. Pase del primer elemento a la variable auxiliar
Gráfica 6. Pase del primer elemento a la variable auxiliar
Es decir: t = X[i]
Luego se copia el valor del segundo elemento del par X[j] sobre el primer elemento X[i]:
Gráfica 7. Pase del segundo elemento al primer elemento.
Es decir: X[i] = X[j]
Finalmente, se copia el valor de la variable auxiliar (t) sobre el segundo elemento X[j]:
Gráfica 8. Pase de la variable auxiliar al segundo elemento
Es decir: X[j] = t
Los elementos quedarán ordenados de la siguiente manera:
Gráfica 9. Pase del segundo elemento al primer elemento.
5) Estos pasos se repiten hasta tener todos los elementos ordenados.
2.2. Ordenamiento por Selección
Este método consiste en seleccionar el menor elemento del arreglo y colocarlo en la primera ubicación mediante el intercambio de valores.
Entre los elementos restantes nuevamente se busca el menor y lo colocamos en la segunda ubicación, mediante el intercambio de valores, y así sucesivamente, hasta tener todos los elementos ordenados.
La técnica consiste en lo siguiente:
1) Se definen dos subíndices (i y j), el primero para definir el número de búsqueda por el arreglo y el segundo el número de comparación para encontrar el menor elemento.
2) Se determina el rango de cada subíndice, teniendo en cuenta que, aunque hay (n=4) elementos en el arreglo, solamente se necesitan (n-1=3) búsquedas.
Así mismo, teniendo en cuenta que el menor elemento de la búsqueda i siempre comenzará a compararse con el siguiente elemento del arreglo (j=i+1) y terminará con el último (n); entonces, el número de comparaciones en cada búsqueda es (n-i).
Por lo tanto, los rangos de cada subíndice son:
i : 1 .. n-1 j : i+1 .. N
Luego, los bucles a utilizar son los siguientes:
Para i=1 Hasta n-1 Variación 1
Para j=i+1 Hasta n Variación 1
3) La primera vez que se ejecuta el bucle i (es decir i=1) se hace lo siguiente:
k=1 [Subíndice del menor elemento]
menor = X[1]
Aquí se supone que el menor elemento del arreglo es el primero (índice 1).
4) Se inicia el bucle j (j=2), que sirve para buscar el menor elemento de todos, para lo cual se realiza la siguiente comparación:
Si X[2]<menor Entonces
5) Al término del bucle j, k contiene el subíndice del menor elemento y menor contiene el valor del menor elemento, los cuales serán intercambiados a la primera ubicación no ordenada mediante las siguientes sentencias:
X[k] = X[i]
X[i] = menor
Estos pasos se repiten hasta tener todos los elementos ordenados.
2.3. Ordenamiento por Inserción
Esta técnica también se denomina “método del jugador de cartas”, por su semejanza con la forma de clasificar las cartas de una baraja insertando cada carta en el lugar adecuado. En esta ordenación, en cada etapa ya se tiene una lista ordenada, pero más pequeña.
El algoritmo de ordenación por inserción ordena los dos primeros elementos de la lista, a continuación el tercer elemento se inserta en la posición que corresponde, el cuarto se inserta en la lista de tres elementos, y así sucesivamente. Este proceso continúa hasta que la lista este totalmente ordenada.
El procedimiento es el siguiente:
1) Al primer elemento (i=1) no se le modifica su ubicación, y a los elementos restantes, que se desean insertar, sus ubicaciones variarán desde i=2 hasta n.
2) Para (i=2), este elemento se asigna a una variable auxiliar (t). El dato almacenado en t se compara con el elemento almacenado en X[1]. Si t es menor que X[1], entonces X[1] se transfiere a X[2] y t a X[1]. Si no t se transfiere a X[2].
3) Comparar X[3] con X[2]. Si X[3] es mayor o igual que X[2] entonces se continúa con el siguiente elemento, si no se compara X[3] con X[1]. Si X[3] es mayor o igual que X[1], entonces X[3] se transfiere a t, X[2] a X[3] y t a X[2]. Si X[3] es menor que X[1], entonces se transfiere X[1] a t, X[3] a X[1], X[2] a X[3] y t a X[2].
4) Repetir los pasos anteriores hasta completar el ordenamiento.
2.4. Ordenamiento Shell
Es un método de ordenamiento muy rápido, fue desarrollado por Donald Shell (1959), el procedimiento es sencillo y corto, pero su comprensión no lo es y se basa en una sucesión de clasificaciones. Es una mejora del método de inserción directa basada en la disminución de los incrementos o saltos. Se comparan los elementos dos a dos: X[i] con X[i+n/2] y se les ordena.
Se hacen las mismas comparaciones pero de la forma: X[i] con X[i+n/2] y se les ordena. Luego se hacen las mismas comparaciones pero de la forma: X[i] con X[i+n/4] y también se les ordena. Este proceso continúa hasta que se obtiene la clasificación final. El procedimiento es:
1) Se selecciona el salto o intervalo en el arreglo original (k=n/2), se forman grupos de dos elementos cada uno (posiciones [j] y [j+k]) y se clasifica cada grupo por separado (compara parejas de elementos, si no están ordenados se intercambian de posiciones entre sí).
Se realiza una o más repasadas en esta operación hasta comprobar que ya no se requiere intercambios de posiciones.
2) Se selecciona un nuevo salto para el arreglo obtenido en el paso anterior (k=k/2), se forman grupos de dos elementos cada uno y se clasifica cada grupo por separado. Se realiza una o más repasadas hasta comprobar que ya no se requieren intercambios de posiciones.
3) El procedimiento se repite hasta que el salto sea k=1. Completándose el ordenamiento con las repasadas necesarias hasta comprobar que ya no se requieren intercambios de posiciones.
Ejemplo:
Ingresar el tamaño de un vector y cada uno de sus elementos. Ordenar los elementos del vector en forma ascendente usando el método 2 de la burbuja.
Codificación:
#include <iostream.h> // Ordenamiento por burbuja – metodo 2
#include <conio.h>
main() {
int n; // Número de elementos del vector
int i; // Contador que al inicio indica los elementos de vector no ordenado
int j; // Contador de elementos que se van a comparar e intercambiar
int t; // Variable auxiliar usada para el intercambio de valores
int x[20]; // Elemento del vector
clrscr();
gotoxy(15,2); cout<<"Tamaño del vector";
gotoxy(41,2); cin>>n;
gotoxy(15,4); cout<<"Elementos del vector";
for(i=1;i<=n;i++) {
gotoxy(15,5+i); cout<<"Elemento N° "<<i<<" : ";
gotoxy(41,5+i); cin>>*(x+i); // Ingreso de datos del vector
}
for(i=1;i<=n-1;i++) { // Ordenamiento del vector
for(j=i+1;j<=n;j++) {
if(*(x+i)>*(x+j)) { // Comparación de valores
t=*(x+i); // Intercambio de valores
*(x+i)=*(x+j);
*(x+j)=t; }
}
}
clrscr();
cout<<"Vector Ordenado";
for(i=1;i<=n;i++) {
gotoxy(10,3+i); cout<<*(x+i); // Reporte del arreglo ordenado
}
getch();
}
3. Búsqueda
La búsqueda (search en inglés) es un proceso que permite determinar si un arreglo contiene un valor que sea igual a cierto valor clave.
Existen dos técnicas de búsqueda:
- Búsqueda lineal
- Búsqueda binaria
3.1. Búsqueda Lineal
La búsqueda lineal es la técnica más simple y funciona bien con arreglos pequeños y no ordenados.
Consiste en comparar la clave de búsqueda con todos los elementos del arreglo.
Por ejemplo, buscar el valor clave = 5 en el arreglo:
X[i] = [8 3 5 7].
Gráfica 10. Comparación de la clave con cada uno de los elementos.
El procedimiento es el siguiente:
1) Inicialmente a la posición del elemento buscado (p) se le asigna un valor que no corresponde a ningún valor posible del subíndice del arreglo, tal como, -1.
p = -1
2) Se genera un bucle que permita comparar la clave con cada uno de los elementos del arreglo:
Para i=1 Hasta n Variación 1 Hacer Si clave = X[1] Entonces p = i
3) Si el resultado de la comparación es verdadera para un valor del subíndice del arreglo, entonces este valor será la posición del elemento buscado; en el ejemplo, p=3.
4) En el caso de que el valor inicial de p no varié, después de haberse realizado todas las comparaciones, implica que el valor buscado no existe en el arreglo.
3.2. Búsqueda Binaria
La búsqueda binaria es la técnica de más alta velocidad y funciona eficientemente con arreglos grandes y ordenados previamente.
Consiste en eliminar, tras cada comparación, la mitad de los elementos del arreglo en los que se efectúa la búsqueda.
Primero localiza el elemento central del arreglo y luego lo compara con la clave de búsqueda.
Si son iguales, se ha encontrado dicha clave y se devuelve el subíndice de ese elemento.
De otro modo, el problema se reduce a buscar en una mitad del arreglo.
Ejemplo:
Ingresar el tamaño de un vector y cada uno de sus elementos. Así mismo, ingresar un número y en el caso de que éste se encuentre dentro del vector, reportar la posición que ocupa. En caso contrario, reportar el mensaje: “El elemento buscado no ha sido encontrado”. Usar el método de búsqueda lineal.
Codificación:
#include <iostream.h> // Búsqueda lineal
#include <conio.h>
main() {
int n; // Número de elementos del vector
int i; // Contador de los elementos del vector
int clave; // Valor que será buscado en el arreglo
int p; // Posición del elemento buscado
int x[20]; // Elementos del vector
clrscr();
gotoxy(5,2); cout<<"Tamaño del vector";
gotoxy(30,2); cin>>n;
gotoxy(5,4); cout<<"Elementos del vector";
for(i=1;i<=n;i++) {
gotoxy(5,5+i); cout<<"Elemento N° "<<i<<" : ";
gotoxy(30,5+i); cin>>*(x+i); // Ingreso de los elementos del vector
}
clrscr();
gotoxy(5,2); cout<<"Ingrese el número a buscar: ";
gotoxy(40,2); cin>>clave; // Introducción de una clave de búsqueda
p=-1;
for(i=1;i<=n;i++) if(*(x+i)==clave) p = i; // Ubicación de la posición del número buscado
if(p!=-1) {
gotoxy(5,5); cout<<"El elemento buscado se encuentra en la posición: "<<p; }
else {
gotoxy(5,5); cout<<"El elemento buscado no ha sido encontrado"; }
getch();
}
4. Mezcla
La mezcla o fusión (merge en inglés) consiste en tomar dos arreglos (X[i] e Y[j]) ordenados previamente y obtener un nuevo arreglo (Z[h]) también ordenado a partir de la intercalación de ambos. El algoritmo más sencillo para resolver el problema consiste en:
Situar todos los elementos de X en el nuevo vector Z.
Situar todos los elementos Y en el nuevo vector Z.
Ordenar todo el vector Z.
Evidentemente esta es una solución correcta. Sin embargo se ignora por completo el hecho de que los arreglos X e Y están clasificados, lo que supondrá una ralentización (reunión) del proceso en el tiempo.
El proceso correcto consiste en lo siguiente:
1) Inicializar los subíndices de los tres arreglos X, Y e Z, es decir: i=1, j=1 y h=1 respectivamente.
2) Siempre que los subíndices de los dos arreglos iniciales X e Y (es decir, i y j respectivamente), sean menores que sus tamaños (M y N), comparar los elementos respectivos de ambos arreglos y seleccionar el elemento que tiene el menor valor.
Gráfica 11. Mezcla de dos vectores.
Gráfica 11. Mezcla de dos vectores.
3) Ubicar el elemento seleccionado en el paso anterior en el nuevo arreglo Z y el subíndice del arreglo seleccionado (i ó j) incrementar en 1.
4) Incrementar el subíndice de arreglo resultante h en 1.
5) Seguir esta secuencia de comparaciones hasta que los elementos de uno de los arreglos se haya agotado, es decir, hasta que el valor del subíndice de dicho arreglo sea mayor que su tamaño.
6) Copiar el resto de elementos del arreglo no agotado en el arreglo resultante Z, sin olvidar que el subíndice del arreglo resultante (h) se deberá continuar incrementando en 1; hasta obtener, finalmente, su tamaño de M + N elementos.
Ejemplo:
Ingresa dos vectores, ordenarlos en forma descendente, luego obtener y reportar un nuevo vector formado por la mezcla o fusión (merge) de los dos anteriores, también ordenado en forma decreciente.
Codificación:
#include <iostream.h> // Mezcla de vectores
#include <conio.h>
#define lim 20
main() {
int a, b; // Tamaño de lo vectores
int i, j; // Subíndices de los vectores
int h, k; // Subíndices auxiliares de los vectores
int g; // Subíndice del vector mezcla
int r, t; // Variables auxiliares para ejecutar intercambios en el ordenamiento
int p; // Subíndice para el resto del vector no agotado
int x[lim]; // Elementos del primer vector
int y[lim]; // Elementos del segundo vector
int z[lim]; // Elementos del vector mezcla
do {
clrscr();
gotoxy(5,2); cout<<"Tamaño del primer vector :";
gotoxy(40,2); cin>>a;
gotoxy(5,4); cout<<"Tamaño del segundo vector :";
gotoxy(40,4); cin>>b; }
while(a<=0 && b<=0);
clrscr();
cout<<"\n\nINGRESO DE DATOS DE PRIMER VECTOR\n\n";
cout<<"Número Dato";
for(i=1;i<=a;i++) {
gotoxy(3,5+i); cout<<i;
gotoxy(13,5+i); cin>>*(x+i); }
clrscr();
cout<<"\n\nINGRESO DE DATOS DE SEGUNDO VECTOR\n\n";
cout<<"Número Dato";
for(j=1;j<=b;j++) {
gotoxy(3,5+j); cout<<j;
gotoxy(13,5+j);cin>>*(y+j); }
for(i=1;i<=a-1;i++) { // Ordenamiento del primer vector
for(h=i+1;h<=a;h++) {
if(*(x+i)>*(x+h)) {
r=*(x+i); *(x+i)=*(x+h); *(x+h)=r; }
}
}
for(j=1;j<=b-1;j++) { // Ordenamiento del segundo vector
for(k=j+1;k<=b;k++) {
if(*(y+j)>*(y+k)) {
t = *(y+j); *(y+j) = *(y+k); *(y+k) = t; }
}
}
i=1; // Valor inicial del subíndice del primer vector
j=1; // Valor inicial del subíndice del segundo vector
g=1; // Valor inicial del subíndice del vector mezcla
while(i<=a && j<=b) { // Mezclar los vectores
if(*(x+i)<=*(y+j)) { // Ingreso de elementos del primer vector al vector mezcla
*(z+g)=*(x+i); i=i+1;
}
else { // Ingreso de elementos del segundo vector al vector mezcla
*(z+g)=*(y+j); j=j+1;
}
g=g+1; // Incremento del subíndice del vector mezcla
}
// En este instante, los elementos de alguno de los arreglos pudieron no haberse agotado
// Para superar este problema, se copia el resto del vector no agotado
if(i>a) { // Cuando subíndice de 1er. vector llega a ser mayor que su tamaño
for(p=j; p<=b; p++) {
*(z+g)=*(y+p); g=g+1; }
}
else { // Cuando subíndice de segundo vector llega a ser mayor que su tamaño
for(p=i; p<=a; p++) {
*(z+g)=*(x+p); g=g+1; }
}
clrscr();
cout<<"\n\nDATOS DEL VECTOR MEZCLADO\n\n";
cout<<"Número Dato";
for(g=1;g<=a+b;g++) {
gotoxy(3,5+g);cout<<g;
gotoxy(13,5+g);cout<<*(z+g); // Reporte del vector mezcla
}
getch();
}
No hay comentarios:
Publicar un comentario