Estructura de Datos II

1.1 Introducción y clasificación de los algoritmos

Algoritmo
Es una secuencia de pasos lógicos finitos para resolver un problema.

Clasificación de los algoritmos

Los algoritmos con el manejo de la información se clasifican en :

a) De ordenación
b) De búsqueda

Ambos procesos pueden clasificarse como internos o externos dependiendo del lugar en el que se encuentre almacenada la información.

Los internos se llevan a cabo en memoria principal; los externos se realizan en memoria secundaria (Discos flexibles, cintas, discos duros, etcétera).

La operación de búsqueda es la que permite recuperar datos previamente almacenados. Ordenar significa reorganizar un conjunto de datos u objetos de acuerdo a una secuencia específica. El proceso de ordenación es importante cuando requiere optimizarse un proceso de búsqueda.

Formalmente definimos ordenación de la siguiente manera:

Sea A una lista de n elementos Ao, A1, A2,…,An.

La lista A estará ordenada después de aplicarle un proceso logramos que:

a) Ao <= A1 <= A2 … <=An (ordenamiento ascendente)
b) Ao>= A1 >= A2 …>= An (ordenamiento Descendente)

Un método de ordenación es estable si el orden relativo de elementos iguales permanece inalterado durante el proceso de ordenación. La estabilidad es conveniente si los elementos ya se encontraban ordenados conforme a algún otro campo.

Un método de ordenación es inestable si se altera el orden relativo de elementos iguales durante el proceso de ordenación.

2.1 Clasificación por Inserción Directa

El método de ordenación por inserción directa es el que generalemente utilizan los jugadores de cartas cuando ordenan éstas, de ahí que tambien se conozca con el nombre de método de la baraja.

La idea central de este algoritmo consiste en insertar un elemento del arreglo en la parte izquierda del mismo, que ya se encuentra ordenada. Este proceso se repite desde el segundo hasta el n-ésimi elemento.

Ejemplo:
Supongase que se desea ordenar las siguientes claves del arreglo A utilizando el método de inserción directa.

A: 15 67 08 16 44 27 12 35

PRIMERA PASADA

A[2]<A[1] (67<15) no hay intercambio

A: 15 67 08 16 44 27 12 35

SEGUNDA PASADA

A[3]<A[2] (08<67) sí hay intercambio
A[2]<A[1] (08<15) sí hay intercambio

A: 08 15 67 16 44 27 12 35

TERCERA PASADA

A[4]<A[3] (16<67) sí hay intercambio
A[3]<A[2] (16<15) no hay intercambio

A: 08 15 16 67 44 27 12 35

Obsérvese que una vez que se determina la posición correcta del elemento se interrumpen las comparaciones. Por ejemplo, en el caso anterior no se realizó la comparación A[2]<A[1].

Las restantes pasadas se presentan a continuación:

image2.gif (2899 bytes)

void insercion_directa(int n)
{
int i,j,aux;
i=j=1;
for(;j<n;j++)
for(i=j;i > 0 && (arr[i] < arr[i-1]); i–)
{
aux=arr[i];
arr[i]=arr[i+1];
arr[i+1]=aux;
}
}

2.2 Clasificación por Selección Directa

El método de ordenación por selección directa es más eficiente que los métodos analizados anteriormente.
Pero, unque su comportamiento es mejor que el de aquéllos y su programación es fácil y comprensible, no es recomendable utilizarlo cuando el número de elementos del arreglo es medio grande.

La idea básica de este algoritmo consiste en buscar el menor elemento en el arreglo y colocarlo en primera posición. Luego se busca el segundo elemento más pequeño del arreglo y se lo coloca en segunda posición. El proceso continua hasta que todos los elementos del arreglo hayan sido ordenados. El método se basa en los siguientes principios:

1. Seleccionar el menor elemento del arreglo.
2. Intercambiar dicho elemento con el primero.
3. Repetir los pasos anteriores con los (n-1), (n-2 ) elementos y así sucesivamente hasta que sólo         quede el elemento mayor.

Ejemplo:

Supongase que se desea ordenar las siguientes claves del arreglo
A: 15 67 08 44 27 12 35

void seleccion_directa(int n)
{
int i,j,min,k;
int cambio;
for(i=0;i<n;i++)
{
min=arr[i];
k=0;
cambio=0;
for(j=i+1;j<n;j++)
{
if (arr[j]<min)
{
min=arr[j];
k=j;
cambio=1;}
}
if (cambio )
{
arr[k]=arr[i];
arr[i]=min;
}
}
}

2.3 Clasificación por Intercambio Directo (Burbuja).

El método de intercalación directo, conocido coloquialmente con el nombre de la burbuja, es el más utilizado entre los estudiantes de computación, por su fácil compresión y programación. Pero es preciso señalar que es probablemente el método más ineficiente.

El método de intercambio directo puede trabajar de dos maneras diferentes. Llevando los elementos más pequeños hacia la parte izquierda del arreglo o bien llevando los elementos más grandes hacia la parte derecha del mismo.

La idea básica de este algoritmo consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentran ordenados. Se realizan (n-1) pasadas, transportando en cada una de las mismas el menor o mayor elemento (según sea el caso) a su posición ideal. Al final de las (n-1) pasadas los elementos del arreglo estarán ordenados.

Ejemplo :
Supóngase que desean ordenar las siguientes claves del arreglo A, transportando en cada pasada el menor elemento hacia la parte izquierda del arreglo.

A: 15 67 08 16 44 27 12 35

Las comparaciones que se realizan son las siguientes:

PRIMERA PASADA

a[7]>a[8] (12>35) no hay intercambio
a[6]>a[7] (27>12) si hay intercambio
a[5]>a[6] (44>12) si hay intercambio
a[4]>a[5] (16>12) si hay intercambio
a[3]>a[4] (08>12) no hay intercambio
a[2]>a[3] (67>08) si hay intercambio
a[1]>a[2] (15>08) si hay intercambio

Luego de la primera pasada el arreglo queda de la siguiente forma:

A: 08 15 67 12 16 44 27 35

Obsérvese que el elemento 08 fue situado en la parte izquierda del arreglo.

SEGUNDA PASADA

a[7]>a[8] (27>35) no hay intercambio
a[6]>a[7] (44>27) si hay intercambio
a[5]>a[6] (16>27) no hay intercambio
a[4]>a[5] (12>16) no hay intercambio
a[3]>a[4] (67>12) si hay intercambio
a[2]>a[3] (15>12) si hay intercambio

Luego de la segunda pasada el arreglo queda de la siguiente forma:

A: 08 12 15 67 16 27 44 35

y el segundo elemento más pequeño del arreglo, en este caso 12, fue situado en la segunda posición.

A continuación se muestra el resultado de las siguientes pasadas:

3era. Pasada : 08 12 15 16 67 27 35 44
4ta. Pasada : 08 12 15 16 27 67 35 44
5ta. pasada : 08 12 15 16 27 35 67 44
6ta. Pasada : 08 12 15 16 27 35 44 67
7ma. Pasada : 08 12 15 16 27 35 44 67

El algoritmo de ordenación por el método de intercambio directo que transporta en cada pasada el menor elemento hacia la parte izquierda del arreglo es el siguiente :

void Intercambio_Directo(int n)
{
int i,j,aux;
i=0;
j= n-1;
for(;j>0;j–)
for(i=0;i<j;i++)                //recorre el arreglo de 0 a n-1
{
if (arr[i]>arr[i+1])        //si el elemento actual es mayor que el elemento siguiente
{
aux=arr[i];             //intercambio de elementos
arr[i]=arr[i+1];
arr[i+1]=aux;
}
}
}

ANÁLISIS DE EFICIENCIA DEL MÉTODO DE INTERCAMBIO DIRECTO

El número de comparaciones en el método de la burbuja es fácilmente contabilizable. En la primera pasada realizamos (n-1) comparaciones, en la segunda pasada (n-2) comparaciones, en la tercera pasada (n-3) comparaciones y así sucesivamente hasta llegar a 2 y 1 comparaciones entre claves, siendo n el número de elementos del arreglo. Por lo tanto:

C = (n-1) + (n-2) +…+2 + 1 = (n*(n-1))/2

que es igual a:

C = (n2 -n)/2

Respecto al número de movimientos, éstos dependen de si el arreglo está ordenado, desordenado o en orden inverso. Los movimientos para cada uno de estos casos son:

Mmin = 0

Mmed = 0.75 * (n2 – n)

Mmáx = 1.5 * (n2 – n)

Así por ejemplo si tiene que ordenarse un arreglo que contiene 500 elementos, se efectuará :

Si el arreglo se encuentra ordenado :

124 750 comparaciones
0 movimiento

Si los elementos del arreglo se encuentran dispuestos en forma aleatoria :

124 750 comparaciones
187 125 movimientos

Si los elementos del arreglo se encuentran en orden inverso:

124 750 comparaciones
374 250 movimientos

Ahora bien, el tiempo necesario para ejecutar el algoritmo de burbuja es proporcional a n2, donde n es el número de elementos del arreglo.

2.4 Clasificación por Vibración(Shaker Sort)

La idea básica de este algoritmo consiste en mezclar las dos formas en que se puede realizar el método de la burbuja. En este algoritmo cada pasada tiene dos etapas. En la primera etapa “de derecha a izquierda” se trasladan los elementos más pequeños hacia la parte izquierda del arreglo, almacenando en una variable la posición del último elemento intercambiado. Las sucesivas pasadas trabajan con los componentes del arreglo comprendidos entre las posiciones  almacenadas en las variables. El algoritmo de la variable que almacena el extremo izquierdo del arreglo es mayor que el contenido de la variable que almacena el extremo derecho.

Ejemplo:
Supongase que desea ordenarse las siguientes claves del arreglo A utilizando el método de la sacudida.

A: 15 67 08 44 27 12 35

PRIMERA PASADA

Primera etapa (de derecha a izquierda).

A[7]>A[8] (12>35) no hay intercambio
A[6]>A[7] (27>12) sí hay intercambio
A[5]>A[6] (44>12) sí hay intercambio
A[4]>A[5] (16>12) sí hay intercambio
A[3]>A[4] (08>12) no hay intercambio
A[2]>A[3] (67>08) sí hay intercambio
A[1]>A[2] (15>08) sí hay intercambio

Última posición de intercambio de derecha a izquierda : 2
Luego de la primera etapa de la primera pasada, el arreglo queda de la siguiente forma:

A: 08 15 67 12 16 44 27 35

Segunda etapa (de izquierda a derecha)

A[2]>A[3] (15>67) no hay intercambio
A[3]>A[4] (67>12) no hay intercambio
A[4]>A[5] (67>16) no hay intercambio
A[5]>A[6] (67>44) no hay intercambio
A[6]>A[7] (67>27) no hay intercambio
A[7]>A[8] (67>35) no hay intercambio

Última posición de intercambio de izquierda a derecha : 8

Luego de la segunda etapa de la primera pasada, el arreglo queda de la siguiente forma:

A: 08 15 12 16 27 35 67

SEGUNDA PASADA

A[6]>A[7] (27>35) no hay intercambio
A[5]>A[6] (44>27) sí hay intercambio
A[4]>A[5] (16>27) no hay intercambio
A[3]>A[4] (12>16) no hay intercambio
A[2]>A[3] (15>12) sí hay intercambio

Última posición de intercambio d ederecha a izquierda : 3

A: 08 12 15 16 276 44 35 67

Segunda etapa (de izquierda a derecha)

A[3]>A[4] (15>16) no hay intercambio
A[4]>A[5] (16>27) no hay intercambio
A[5]>A[6] (27>44) no hay intercambio
A[6]>A[7] (44>35) sí hay intercambio

Última posición de intercambio de izquierda a derecha : 7

A: 08 12 15 16 27 34 44 67

Al realizar la primera etapa de la tercera pasada se observa que no se realizaron intercambios, por lo tanto la ejeción del algoritmo se termina.

ANÁLISIS DE EFICIENCIA DEL MÉTODO DE LA SACUDIDA

El análisis del método de la sacudida y en general el de los métodos mejorados y logarítmicos son muy complejos. Para el análisis de este método es necesario tener en cuenta tres factores que afectan directamente al tiempo de ejecución del algoritmo: las comparaciones entre las claves, los intercambios entre las mismas y las pasadas que se realizan. Encontrar fórmulas que permitan calcular cada uno de estos factores es una tarea muy difícil de realizar.

Los estudios que se han efectudado sobre el método de la sacudida demuestra que en el mismo, sólo pueden reducirse las dobles comparaciones entre claves; pero debe recordarse que la operación de intercambio es una tarea más complicada y costosa que la de comparación. Por lo tanto, es posible afirmar que las hábiles mejoras realizadas sobre el método de intercambio directo sólo producen resultados apreciables si el arreglo está parcialmente ordenado (lo cual resulta difícil saber de antemano), pero si el arreglo está desordenado el método se comporta, incluso, peor que otros métodos directos como los de inserción y selección.

2.5 Inserción por Incremento Decreciente (Shell)

Este método consiste en subdividir el arreglo original en grupos de elementos mas pequeños. Dichos grupos están compuestos por los elementos separados por k posiciones.

En seguida se aplica el método de ordenación por inserción directa en cada subgrupo el proceso se repite empezando con una k grande y decrementadola en cada iteración hasta llegar a k = 1.

¿QUE INCREMENTOS SON MEJORES?

Una buena política es que las k elegidas no sean múltiplos de si mismas. Knuth sugiere la siguiente secuencia:
1,4,13,40,121,…, (3m-1)/2
1,3,7,15,31,63,127,…,2m -1

Para esta ultima opción se a encontrado que el esfuerzo para este método es del orden de n1.2

void shell(int n)
{
int i,j,m,k,x;
for(m=t;m>0;m–)
{
k=pow(2,m)-1;
for(i=k;i<n;i++)
{
x=arr[i];
j=i-k;
while(x<arr[j]&& j>=0)
{
arr[j+k]=arr[j];
j-=k;
}
arr[j+k]=x;
}
}
}

2.6 Clasificación por Partición (Quicksort)

Este algoritmo es uno de los mejores que se conocen hasta hoy en día. Es una mejora del método de ordenación por intercambio directo y consiste en:

1) Elegir un elemento x al azar
2) Buscar por la izquierda del arreglo un elemento mayor que x
3) Buscar por la derecha un elemento menor o igual que x
4) Si no se han cruzado los índices izquierda y derecha intercambiar el elemento mayor.
5) Repetir desde el paso 2) mientras no se crucen los índices izquierda y derecho.
6) Intercambiar x con el elemento de la derecha
7) En este momento el elemento x divide el arreglo en dos subarreglos tales que el subarreglo izquierdo                  contiene los elementos <= que x y el subarreglo derecho > que x, por lo tanto x esta ordenado.
8) Hacer quicksort con el arreglo izquierdo
9) Hacer quicksort con el arreglo derecho.

void quicksort(int n)
{
int ini, fin ,izq,der,x,aux;
inicio=new nodo;
inicio->inip=0;
inicio->finp=n-1;
inicio->sig=inicio->ant=NULL;
ultimo = inicio;
while(inicio)
{
nuevo=NULL;
ini = ultimo->inip;
fin= ultimo->finp;
if(ultimo==inicio)
{
delete inicio;
último = inicio= NULL;
}
else
{
último = ultimo->ant;
delete ultimo->sig;
último->sig=NULL;
}
izq=ini; der=fin; x=arr[ini];
while(izq<der)
{
while(arr[izq]<=x && izq<der) izq++;
while(arr[der]>x)der–;
if(izq<der)
{
aux= arr[izq];
arr[izq]=arr[der];
arr[der]=aux;
}
}
arr[ini]=arr[der];
arr[der]=x;
if(der+1<fin)
{
nuevo =new nodo;
nuevo->inip=der+1;
nuevo->finp=fin;
if(inicio)
{
último->sig=nuevo;
nuevo->ant=ultimo;
nuevo->sig=NULL;
último=nuevo;
}
else
{
nuevo->sig=nuevo->ant= NULL;
inicio=ultimo=nuevo;
}
}
if(ini<der-1)
{
nuevo = new nodo;
nuevo->inip=ini;
nuevo->finp=der-1;
if(inicio)
{
ultimo->sig=nuevo;
nuevo->ant=ultimo;
nuevo->sig=NULL;
ultimo=nuevo;
}
else
{
nuevo->sig=nuevo->ant=NULL;
inicio=ultimo=nuevo;
}
}
}
}

void Quicksort_Recursivo(int ini, int fin)
{
int izq,der,x,aux;
x=arr[ini];
izq=ini;der=fin;
while(izq<der)
{
while(arr[izq]<=x &&izq<der) izq++;
while(arr[der]>x)
der–;
if (izq<der)
{
aux= arr[izq];
arr[izq]=arr[der];
arr[der]=aux;
}
}
arr[ini]=arr[der];
arr[der]=x;
if(ini<der-1)sort_rec(ini,der-1);
if(der+1 <fin)sort_rec(der+1,fin);
}

}

}

2.7 Clasificación por árbol (Heapsort)

Un montón se define como una secuencia de elementos hini, hini+1,…,hfin, tales que hp>h2p+1, hp>=h2p+2 y ho = max(ho,h1,…,hn).

void Heapsort(int n)
{
int ini,fin;
fin=n-1;
ini=n/2;
int aux;
while(ini>0)
{
ini–;
monton(ini,fin);
}
while(fin!=0)
{
aux=arr[0];
arr[0]=arr[fin];
arr[fin]=aux;
fin–;
monton(ini,fin);
}
}

void monton(int ini, int fin)
{
int p,h;
p=ini;
h=2*p+1;
int aux;
if(h<fin&&arr[h]<arr[h+1])h++;
while(arr[p]<arr[h]&&h<=fin)
{
aux=arr[p];
arr[p]=arr[h];
arr[h]=aux;
p=h;
h=2*p+1;
if(h<fin&&arr[h]<arr[h+1])h++;
}
}

Referencia: http://www.itlp.edu.mx/tutoriales

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s