jueves, 6 de noviembre de 2008

Métodos de ordenación

Fuente http://mx.geocities.com/developer_webs/temario.htm

Método de la burbuja
Es uno de los métodos más extendidos y más fáciles, pero a la vez es uno de los menoseficaces.

Este método se basa en la ordenación por cambio de elementos, ya que se van comparando de dos en dos los elementos de la tabla. Si nosotros deseamos ordenar dicha tabla de menor a mayor (ascendente) al realizar la comparación entre dos elementos se produce el intercambio en el momento en el que el primer elemento es mayor que el segundo. De esta forma el elemento más grande pasa a estar en el último lugar de la tabla. El elemento sube por la tabla, al igual que una burbuja en un recipiente, de ahí proviene su nombre.

Los pasos a seguir utilizando este método son los siguientes, imaginando que deseamos realizar una ordenación creciente:

1.- Se compara el primer elemento con el segundo. Si están desordenados se intercambian. Luego se mira el segundo con el tercero, intercambiando también si es necesario. Así hasta que llegamos al último elemento. De esta forma tenemos en la última posición de nuestra tabla el elemento más grande.

2.- Repetimos lo mismo que antes pero ahora con todos los elemento, menos el último, que ya está ordenado.

3.- Repetimos el primer paso pero esta vez con otro elemento menos, ya que este también está ordenado. Este método finaliza en el momento en el que se han realizado tantas pasadas como objetos - 1 hay en la lista. Su hace menos 1 pasadas porque el primero de los objetos, como es lógico si pensamos que los demás ya están ordenados, ya está ordenado.
Vamos a ver el código que escribiríamos para utilizar este método:

1-Indice = 1
2-Repetir
3-Mientras Indice2 <> TotalElem - 1 hacer
4-Si Tabla(Indice2) > Tabla(Indice + 1) Entonces
5-Intercambiar Tabla(Indice2), Tabla(Indice2 + 1)
6-Fin Si
7-Indice2 = Indice2 + 1
8-Fin Mientras
9-Hasta que Indice > TotalElem - 1

Vamos a comentar como funcionaría este código:

En la línea 1 iniciamos una variable llamada Indice a 1, ya que vamos a suponer que nuestra tabla empieza a contar en el 1, esta variable es la que nos controlará cuando se acaba nuestra ordenación. La ordenación finalizará cuando el valor de Indice sea mayor que el número total de elementos (aquí representado por TotalElem) menos 1, (Mirar línea 9). Ya que como hemos dicho antes suponemos que en la última pasada, solo existirá un elemento a mirar y por lo tanto ya estará ordenado.
En la línea 2 iniciamos un bucle Repetir... Hasta que que termina en la línea 9. Este bucle terminará en el momento en el que el Indice tenga como valor el total de elementos TotalElem menos 1. Ya que entonces terminará la ordenación.
En la línea 3 iniciamos otro bucle que está situado dentro del primero. Este se repetirá para ir comparando de dos en dos los diferentes elementos de la tabla. Se repetirá mientras Indice2 sea diferente del total de elementos menos 1 (TotalElem - 1). Hacemos que sea TotalElem - 1 porque así nos aseguramos que en ningún momento nos salgamos del índice de la tabla. Este bucle termina en la línea 8.
En la línea 4 miramos si el elemento que ocupa la posición Indice2 de la tabla, es más grande que el siguiente elemento (Indice + 1). Este Si termina en la línea 6, en un principio no sería necesario ya que solo tenemos una instrucción el Si, pero así facilitamos un poco el entendimiento de la estructura.
En la línea 5, utilizamos una nueva instrucción llamada Intercambiar. Esta instrucción lo que nos hace es cambiar los elementos que ocupan dos posiciones determinadas de la tabla. Estos elementos los separaremos entre sí mediante una coma (,). Esta línea se llevará a cabo en el momento que el primer elemento mirado sea más grande que el segundo.
En la línea 7 incrementamos el valor de Indice2, para continuar comparando elementos dentro de la tabla.
Esta sería la estructura básica de la ordenación de elementos de una tabla utilizando el método burbuja. Podemos ver que es un método un poco rudimentario y un poco largo en según que casos.
Imagina que tenemos una tabla de un total de 50 elementos y que desde un principio está ordenada, pero eso nosotros no lo sabemos, por lo que sometemos la tabla a una ordenación. Como te puedes imaginar el programa está empleando un tiempo que nos puede ser útil, para realizar cualquier otro cálculo dentro de la aplicación. Piensa que con una tabla de 50 elementos el programa pasará por el bucle principal 49 veces



Método Shell o Inserción directa

Es una mejora del método de inserción directa, utilizado cuando el array tiene un gran número de elementos. En este método no se compara a cada elemento con el de su izquierda, como en el de inserción, sino con el que está a un cierto número de lugares (llamado salto) a su izquierda. Este salto es constante, y su valor inicial es N/2 (siendo N el número de elementos, y siendo división entera). Se van dando pasadas hasta que en una pasada no se intercambie ningún elemento de sitio. Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1.
Por ejemplo, lo pasos para ordenar el array {40,21,4,9,10,35} mediante el método de Shell serían:

Salto=3:
Primera pasada: {9,21,4,40,10,35} <-- se intercambian el 40 y el 9.
{9,10,4,40,21,35} <-- se intercambian el 21 y el 10.Salto=1:
Primera pasada: {9,4,10,40,21,35} <-- se intercambian el 10 y el 4.
{9,4,10,21,40,35} <-- se intercambian el 40 y el 21.
{9,4,10,21,35,40} <-- se intercambian el 35 y el 40.
Segunda pasada: {4,9,10,21,35,40} <-- se intercambian el 4 y el 9.
Con sólo 6 intercambios se ha ordenado el array, cuando por inserción se necesitaban muchos más.


Método Quicksort

Fuente: http://mx.geocities.com/developer_webs/primer_parcial.htm

Ordenación rápida (quicksort): Este método se basa en la táctica "divide y vencerás"que consiste en ir subdividiendo el array en arrays más pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del array como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el array.
Normalmente se toma como pivote el primer elemento de array, y se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.Por ejemplo, para dividir el array {21,40,4,9,10,35}, los pasos serían:
{21,40,4,9,10,35} <-- se toma como pivote el 21. La búsqueda de izquierda a derecha encuantra el valor 40, mayor que pivote, y la búsqueda de derecha a izquierda encuentra el valor 10, menor que el pivote. Se intercambian:{21,10,4,9,40,35} <-- Si seguimos la búsqueda, la primera encuentra el valor 40, y la segunda el valor 9, pero ya se han cruzado, así que paramos. Para terminar la división, se coloca el pivote en su lugar (en el número encontrado por la segunda búsqueda, el 9, quedando:{9,10,4,21,40,35} <-- Ahora tenemos dividido el array en dos arrays más pequeños: el {9,10,4} y el {40,35}, y se repetiría el mismo proceso. Algoritmo Iniciar I a primero Iniciar J a ultimo seleccionar el elemento pivotecentral ← A ( ( primero + ultimo) /2) repetir 4.a mientras a(I) central hacer
j ←j -1
fin mientras
4.csi I < = J entonces intercambiar a(I), A (J) hasta queI >J
si j > primero,llamar al procedimiento partir, para dividir la sub-lista izquierda(primero. J)
si I <>#includeint funcion(const void *,const void *);void main(){ // Dar valores al array
qsort(array,N,sizeof(array[0]),funcion); // Ordena el array. }int funcion(const void *a,const void *b){ if(*(int *)a<*(int *)b) return(-1); else if(*(int *)a>*(int *)b) return(1); else return(0); }Claramente, es mucho más cómodo usar qsort que implementar toda la función, pero hay que tener mucho cuidado con el manejo de los punteros en la función, sobre todo si se está trabajando con estructuras


Método Radix
Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan. Lo que hacemos es determinar la importancia de los criterios de ordenación y aplicar ordenación estable tantas veces como criterios se tengan, empezando por el criterio menos importante y determinando por el criterio más importante

Fuente: http://iteso.mx/~jpgonzal/ed2a.html

Estructura de datos de montículo
La estructura de montículo consiste en almacenar los registros detal manera que cada llave sea mayor que otras dos llaves en posiciones específicas. A su vez, estas dos llaves deberán de ser mayores que otras dos más y así sucesivamente.

Esta estructura se puede representar en un arreglo en el que colocamos la raíz en la posición 1 y las posiciones de sus hjijos son la 2 y la 3, en el siguiente nivel posiciones 4, 5, 6 y 7, etc. Esta representación es muy práctica porque resulta sencillo viajar de un nodo a su padre o hijo. El padre del nodo en la posición j se encuentra en la posición j/2 (redondeado al entero inferior más cercano si j es non) y susdos hijos en las posiciones 2j y 2j + 1. Un montículo es un árbol binario completo, representado con un arreglo, en el que la llave mayor se encuentra en la primera posición del arreglo.

Para poder construir un montículo es necesario primero desarrollar la operación de inserción como en el siguiente código:

void PQ::upheap (int k)
{
itemType v;
v = a[k]; a[0]= itemMAX;
while (a[k/2] <= v)
{ a[k] = a[k/2]; k = k /2; }
a[kl] = v;
}

void PQ::insert (itemType v)
{ a[++N] = v; upheap (N); }

Para poder realizar las operaciones de reemplazar y remover requerimos de otro procedimiento que nos permita arreglar el montículo de arriba hacia abajo como en el siguiente código:

void PQ::downheap (int k)
{
int j, itemType v;
v = a[k];
while (k <= N/2)
{
j = k + k;
if (j < N && a[j] < a[j + 1]) j++;
if (v >= a[j]) break;
a[k] = a[j]; k = j;
}
a[k] = v;
}

itemType PQ::remove()
{
itemType v = a[1];
a[1] = a[N--];
downheap (1);
return v;
}

itemType PQ::replace (itemType v)
{
a[0] = v;
downheap (0);
return a[0];
}


Fuente http://mx.geocities.com/developer_webs/ejecutables.htm
Búsqueda por Hash
Es un método de búsqueda que aumenta la velocidad de búsqueda, pero que no requiere que los elementos estén ordenados. Consiste en asignar a cada elemento un índice mediante una transformación del elemento. Esta correspondencia se realiza mediante una función de conversión, llamada función hash.

No hay comentarios: