Analisis de metodos de ordenación

Análisis de Ordenación

Burbuja:

La ordenación por burbuja es una ordenación donde cada iteración pone el elemento más pequeño no ordenado en su lugar correcto, pero también hace cambios en los demás elementos del arreglo. La primera iteración pondrá el elemento más pequeño del arreglo en la primera posición. Se comienza con el elemento más pequeño en la posición N-ésima y se comparanpares de elementos sucesivos, intercambiando cuando el elemento final del par es más pequeño que el que lo precede. De esta manera el elemento menor del arreglo va “burbujeando” (“subiendo”) hasta el tope del arreglo. La siguiente iteración pone el elemento más pequeño de la parte no ordenada del arreglo en la segunda posición, usando la misma técnica.
Hay N-1 comparaciones la primera vezque se pasa por el bucle exterior, N-2 comparaciones la segunda vez, y así sucesivamente. Si el arreglo ya está ordenado, sólo se realizará un paso a lo largo del bucle exterior. En este caso, sólo se requerirán N-1 comparaciones para la ordenación, es el mejor caso posible.
Si el arreglo está ordenado en orden descendente es el peor caso posible y requiere todas las iteraciones posibles delrecorrido del arreglo. Realmente al trabajar con Burbuja se puede decir que su velocidad dependerá de la forma cómo estén ubicados los datos en el arreglo al momento de ejecutarse el ordenamiento. Es decir, la cantidad de trabajo necesario variará, dependiendo del orden de los datos originales.
Para determinar un caso promedio se ha de notar que el número de comparaciones en la iteración Ies N-1. Sea K el número de iteraciones ejecutadas antes de terminar su trabajo. El número total de comparaciones requeridas es
(N – 1) + (N –2) + (N – 3)+ ...+(N – K).
Efectuando un pequeño cambio algebraico de esto da
(2KN –K –K2)/2
Como K no es mayor que N, (2KN –K –K2)/2 es menor o igual que N(N-1)/2. La eficiencia de una algoritmo importa sobre todo en laresolución de problemas de gran tamaño: cuando el tamaño del arreglo crece, el número de comparaciones crece aún más rápido. Se puede expresar una aproximación de esta función usando una notación matemática llamada orden de magnitud, o notación O-grande. El orden de magnitud de una función es la misma que el orden (exponente) del término de la función que crece más rápido respecto al tamaño del problema.Por ejemplo, si
F(N) = N4 + 100N2 + 10N + 50
entonces f(n) es de orden N4 - O, en notación O-grande, O(N4). Esto es, para valores grandes de N, N4 dominará la función. Para valores grandes de N, N4 es mucho mayor que 50 , 10N, o incluso 100 N2 , por tanto se pueden ignorar los otros términos. Esto no significa que los otros término no contribuyan al tiempo de computación; sólo significaque ellos no son significativos en nuestra aproximación.

Merge:

La mezcla (merge) de dos mitades es una tarea O(N): Tan sólo se va a través de las dos mitades ordenadas, comparando pares sucesivos de valores (no para cada mitad) y poniendo el valor más pequeño en la siguiente locación de la solución final. La ordenación de dos medios arreglos tiene menos trabajo que la ordenación de unarreglo completo. Su trabajo mayor aparece en el proceso de mezcla. Se hacen comparaciones sobre cada elemento de los subarreglos; se vuelven a copiar todos los elementos desde Temporal a la lista original, que es también O(N).
Dentro del procedimiento, la rutina se llama después que el arreglo ha sido dividido por la mitad y cada una de esas mitades han sido ordenadas. En cada una de lasllamadas recursivas ( una para la mitad izquierda y otra para la derecha), el arreglo se divide por la mitad de nuevo. Cada mitad es nuevamente subdividida. En cada nivel el número de subarreglos se dobla. Se puede seguir dividiendo el arreglo por la mitad log2N veces, y cada vez se efectúa el procedimiento mezclar de O(N). Esto da un producto de N x log2N. Así, el algoritmo entero es O(N log2...