martes, 4 de noviembre de 2008

Diferentes Métodos de ordenación

Método de ordenación Burbuja

void bubble(int *start, int *end) //Ordena un conjunto de números enteros de menor a mayor
{ short fin;
do
{ fin=0;
for (int *i=start;i!=*end;i++)
{
if (*i>*(i+1))
{ intercambia(i, i+1);
fin=1;
}
}
} while
(fin!=1);
}


http://seduca.uaemex.mx/SofEdu/Sim/MetOrd/metodos.html

Inserción Directa. (A,N)

La idea central de este algoritmo consiste en insertar un elemento del arreglo en la parte izquierda del mismo, que ya se encuentra ordenado. Este proceso se repite desde el segundo hasta el n-ésimo elemento.
El algoritmo es el siguiente.
1. Repetir con I desde 2 hasta N... Hacer Aux <-- A[I], K <-- I-1... 1.1

Repetir mientras (Aux <> 1).... Hacer A[K+1] <-- A[K] y K <-- K-1...
1.2 {Fin del ciclo del paso 1.1}... 1.3 Si A[K] lt;= Aux, entonces.......... A[K+1] <-- Aux........ sino........ A[K+1] <-- A[K] y A[K] <-- Aux... 1.4 {Fin del condicional del paso 1.3}2. {Fin del ciclo del paso 1}

Ordenamiento Radix

Ordenamiento de distribución por conteoUn problema que se presenta con frecuencia es el siguiente: "Ordenar un archivo con N registros cuyas llaves son enteros comprendidos entre 0 y M-1". SiM no es muy grande, se puede usar el algoritmo de distribución porconteo. La idea básica es contar el número de veces que serepite cada llave diferente y en una segunda pasada utilizar el conteo paraposicionar los registros en el archivo.

Mezcla

Ordenación por mezcla (Merg Sort).
Intercalación de archivos ó mezcla de archivos.Por intercalación de archivos se entiende la unión o fusión de dos o más archivos ordenados de acuerdo con un determinado campo en un solo archivo.


Monticulo

Ordenación por el método de heapsort
El método de ordenación heapsort es también conocido con el nombre "montículo" en el mundo de habla hispana. Su nombre se debe a su autor J. W. Williams quien lo bautió así. Es el más eficiente de los métodos de ordenación que trabajan con árboles.
La idea central de este algoritmo consiste en lo siguiente:
Construir un montículo.
Eliminar la raíza del montículo en forma repetida.
Definición. un montículo se define como "Para todo nodo del árbol se debe cumplir que su valor de cualquiera de sus hijos".
Para representar un montículo en un arreglo lineal:
El nodo k se almacena en la posición k correspondiente del arreglo.
El hijo izquierda del nodo k, se almacena en la posición 2 * k.
El hijo derecho del nodo k, se almacena en la posición 2 * k+1.
Inserción de un elemento en un montículo.
La inserción de un elemento en un motnículo se lleva a cabo de la siguiente manera:
Se inserta el elemento en la primera posición disponible.
Se verifica si su valor es mayor que el de su padre. Si se cumple está condición entonces se efectúa el intercambio. Sino se cumple está condición, entonces, el algoritmo se detiene y el elemento queda ubicado en su posición correcta en el montículo. Cabe aclarar que el paso 2 se aplica de manera recursiva y desde abajo hacia arriba.
Eliminación de un montículo.
El proceso para obtener los elementos ordenados se efectúa eliminando la raíz del montículo en forma repetida. Ahora bien, los pasos necesarios para lograr la eliminación de la raíz del montículo son los siguientes:
Se reemplaza la raíz con el elemento que ocupa la última posición del montículo .
Se verifica si el valor de la raíz es menor que el valor más grande de sus hijos. Si se cumple la condición entonces se efectúa el intercambio. Sino se cumple la condición entonces el algoritmo se detiene y el elemento queda ubicado en su posición correcta en el montículo.
Cabe aclarar que le paso 2 se aplica de manera recursiva y desde arriba hacia abajo.
El algoritmo es el siguiente.
Montículo (A,N).
{El algoritmo ordena los elementos del arreglo utilizando el método del montículo. A es un arreglo de N elementos}.
1. Llamar al algoritmo INSERTAMONTÍCULO con A y N.2. Llamar al algoritmo ELIMINAMONTÍCULO con Ay N.
Insertamontículo (A,N).
{El algoritmo inserta elementos en un montículo representando como arreglo. A es un arreglo de N elementos.}
1. Repetir con I desde 2 hasta N.. Hacer k <-- I y Band <-- Verdadero.. 1.1 Repetir mientras k > 1 y Band = Verdadero...... Hacer Band <-- Falso...... 1.1.1 Si A[k] A[parte entera (k entre 2)] entonces............ Aux <-- A[parte entera (k entre 2)]............ A[parte entera (k entre 2)] <-- A[k]............ Band <>QuickSort (se estima un 70%), es el único que garantiza que aún en el peor caso su tiempo de ejecución es proporcional a: (n * log n), 0 (n * log n).