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.
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]).
Un valor grande puede moverse hacia abajo del arreglo
muchas posiciones con un solo pase, pero un valor pequeño se moverá hacia
arriba una sola posición.
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].
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.
Luego se copia el valor del segundo elemento del par
X[j] sobre el primer elemento X[i]
Finalmente, se copia el valor de la variable auxiliar
(t) sobre el segundo elemento X[j]
5) Estos pasos se repiten hasta tener
todos los elementos ordenados.
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.
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.
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();
}
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
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].
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.
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();
}
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.
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();
}
muy bueno tu blog salome, es importante señalar el conocimiento de los tipos de busquedas porque hoy en dia es uno de los mas utilizados en la programacion.
ResponderEliminar