Metodos de ordenamiento

Unidad 5 Metodos de ordenamiento? 5.1 Algoritmos de Ordenamiento Internos?
El ordenamiento de los datos implica una importante mejora de la eficiencia en la búsqueda de los mismos.
Existen dos técnicas básicas de ordenamiento: ordenamientos internos y ordenamientos externos. Los métodos de ordenamiento interno se aplican cuando el conjunto de datos a clasificar es lo suficientemente pequeño,de tal forma que pueda caber en memoria principal.
El tiempo requerido para leer o escribir registros no se considera significativo para la evaluación del rendimiento interno. Los métodos de ordenamiento externo se aplican a grandes volúmenes de datos, que residen parcial o totalmente en dispositivos de almacenamiento secundario, tales como los discos. Aquí, el tiempo de acceso de lectura yescritura influye en la determinación de la eficiencia del ordenamiento.
En esta sección analizaremos en detalle seis de los métodos de ordenamiento interno más utilizados y algunos métodos de intercalación de archivos.
5.1.1 Burbuja?
La idea básica de este método de ordenamiento es la de comparar pares de valores de llaves e intercambiarlos si no están en sus posiciones relativas correctas.Como los métodos de selección e inserción vistos anteriormente, el método de burbuja requiere O(n^2) comparaciones. No obstante, el método de la burbuja es frecuentemente usado.
La idea de este método es la de permitir que cada llave flote a su posición adecuada a través de una serie de pares de comparaciones e intercambios con los valores adyacentes. Cada paso haces que una llave suba a suposición final, como una burbuja, en la lista ordenada.
Consideremos otra vez nuestro ejemplo de lista de llaves no ordenadas:

Cada llave se compara con la llave que está encima de ella (en nuestro caso al lado derecho de ella) y se intercambia, si la llave de arriba es más pequeña. Cuando una llave mayor que la llave sujeto se encuentra, la llave sujeto queda encima, y el proceso continúa.Después de la pasada, todas las llaves arriba de la última por intercambiar deberán estar en su posición final. No necesitarán examinarse en pasos posteriores.
La actividad del primer paso sube a 14, a 22 y a 25.

El método de la burbuja en realidad es muy poco recomendado, sin embargo, es muy conocido (tal vez debido a su nombre) y desafortunadamente muy utilizado (puede ser debido a su relativafacilidad de implementación). Su comportamiento es un poco parecido al método de intercambio selectivo, en el cual las llaves más pequeñas bajan al fondo de la lista.

Este método de ordenamiento también puede funcionar con 2 listas, una de llaves desordenadas y otra de llaves ordenadas, pasando el elemento que flota hasta el final a la lista de ordenados, pero para minimizar el espacio utilizado,trabajaremos con una sola lista.

Una implementación del método de ordenamiento por burbuja puede ser el siguiente:
void Burbuja(Lista Numeros, int Largo)
{
int ultimo=Largo-1;
int posicion;
int auxiliar;
while(ultimo>=1)
{
for(posicion=0;posicion<ultimo;posicion++)
{
if(Numeros[posicion]>Numeros[posicion+1])
{
auxiliar=Numeros[posicion];Numeros[posicion]=Numeros[posicion+1];
Numeros[posicion+1]=auxiliar;
};
};
ultimo--;
};
}; |
5.1.2 Quicksort?
Considerado uno de los mejores métodos de ordenamiento, se le atribuye su creación a C.A. R. Hoare (1962).
La idea básica del método Quicksort es la siguiente:
1. Se selecciona una llave en particular de la lista. Esta llave se puede escoger aleatoriamente o haciendo la media de un pequeño conjunto de llavestomados de la lista. El valor óptimo sería aquél que esté precisamente en medio del rango de valores. Esto se hace para evitar el peor caso de Quicksort, que es seleccionar una llave del extremo. No obstante, incluso en el peor de los casos Quicksort funciona correctamente.
2. Se divide la lista en dos partes, una con todos los elementos menores o iguales que la llave seleccionada y otra con...