Laboratorio 3: Algoritmos de ordenación y análisis de complejidad

publicado a la‎(s)‎ 23 may. 2012 19:24 por Hernan Nina Hanco   [ actualizado el 2 may. 2013 7:24 ]
I) OBJETIVOS
  • Implementar algoritmos de ordenación y analizar su complejidad tanto en soluciones iterativas y recursivas.

II) MARCO CONCEPTUAL


Algoritmos de ordenación
La ordenación es muy probable la operación mas importante y mejor estudiada en computación. Principalmente implementaremos algoritmos que realizan la ordenación en la memoria principal, también se puede realizar en el disco duro o en cintas a este tipo de ordenación se conoce como ordenación externa.

Esquemas simples de ordenación o clasificación
Ordenación o clasificación por Burbuja
Uno de los métodos mas simples es la clasificación por burbuja (bubblesort). La idea básica de la clasificación de burbuja es imaginar que los registros a ordenar están almacenados en un arreglo vertical. Los registros con claves menores son “ligeros” y suben. Se recorre varias veces el arreglo de abajo hacia arriba, y al hacer esto, si hay dos elementos adyacentes que no están en orden, esto es, si el “más ligero” está abajo, se invierten. El efecto que produce por esta operación es que el primer recorrido, el registro “más ligero” de todos, es decir, el registro que posee la clave con menor valor, sube hasta la superficie (o parte superior del arreglo). En el segundo recorrido, la segunda clave menor sube hasta la segunda posición, y así sucesivamente.

inicio12345
Pelee
Etna
Krakatoa
Agung
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Santa Elena
Vesubio

Algoritmo

for i=1 to n-1 do
    for j=n to downto i+1 do
        if A[j].clave < A[j-1].clave then
            intercambia(A[j], A[j-1])

Clasificación por Inserción

En el i-ésimo recorrido se “Inserta” el i-ésimo elemento A[i] en el lugar correcto, entre A[1], A[2], … ,A[i-1], los cuales fueron ordenados previamente. Después de hacer esta inserción, se encuentran clasificados los registros colocados en A[1], A[2], … ,A[i].         
inicio23456
-&
Pelee
Etna
Krakatoa
Agung
Vesubio
Santa Elena
-&
Etna
Pelee
Krakatoa
Agung
Vesubio
Santa Elena
-&
Etna
Krakatoa
Pelee
Agung
Vesubio
Santa Elena
-&
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
-&
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
-&
Agung
Etna Krakatoa
Pelee
Santa Elena
Vesubio

Algoritmo
A[0].clave = -
for i=2 to n do
begin
    j=i;
    while A[j]<A[j-1] do
    begin
        intercambia(A[j],A[j-1])
        j=j-1
    end
end

Ordenación y clasificación por selección

En el i-ésimo recorrido se selecciona el registro con la clave mas pequeña, entre A[j],.. ,A[n], y se intercambia con A[i]. Como resultado, después de i pasadas, los i registros menores ocuparán A[1], …, A[i] en el orden clasificado.

inicio12345
Pelee
Etna
Krakatoa
Agung
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Santa Elena
Vesubio

Algoritmo
for i=1 to n-1 do
begin
    {Elegir el menor entre A[i], ..., A[n] e intercambiarlo con A[i] }
    indice_menor = i
    clave_menor = A[i].clave
    for j=i to n do
    begin
        {Comparar la clave con la actual clave menor}
        if (A[j].clave < clave_menor) then
        begin
            clave_menor = A[j].clave
            indice_menor = j;
        end
        intercambia(A[i],A[indice_menor])
    end
end


Complejidad de tiempo de los métodos
Las clasificaciones de burbuja, por inserción y por selección llevan un tiempo O(N2), y llevarán un tiempo &#x1d6c0;(N2) tanto en el peor caso y promedio, en buena parte de las secuencias de entrada de n elementos.

La clasificación por selección es superior a las clasificaciones de burbuja y por inserción.

Limitaciones de los algoritmos simples
la clasificación de shell es una generalización de burbuja de O(N1.5) 

III) PRÁCTICAS DE LABORATORIO
1) Implementar el algoritmo de ordenación Burbuja.

namespace AlgoritmosOrdenacionSimples
{
    class Program
    {
        
        static void Main(string[] args)
        {
            // Un arreglo de elementos 
            int[] arreglo = { 12, 5, 3, 8, 11, 9, 12, 1, 4, 7 };
            // ordenar el arreglo utilizando el método de burbuja
            clasificacionPorBurbuja(ref arreglo);
            // Mostrar el arreglo ordenado
            for (int i = 0; i < arreglo.Length; i++)
            {
                Console.WriteLine("Elemento[{0}]: {1}",i,arreglo[i]);
            }
            Console.ReadKey();
        }
        /*
         * 
         */
        static void clasificacionPorBurbuja(ref int[] arreglo)
        {
            // N recorridos por el arreglo
            for (int i = 0; i < arreglo.Length - 1; i++)
            {
                // Comparar elementos adyacentes para subir
                // elementos de menor valor a la superficie
                for (int j = arreglo.Length-1; j >= i+1; j--)
                {
                    if (arreglo[j] < arreglo[j - 1])
                    {
                        // Permutar o intercambiar elementos del arreglo
                        int temp = arreglo[j];
                        arreglo[j] = arreglo[j - 1];
                        arreglo[j - 1] = temp;
                    }
                }
            }
        }
    }
}

2) Implementar el algoritmo de ordenación por Inserción.

        /*
         * Implementación de la Clasificación por Inserción
         */
        static void clasificacionPorInsercion(ref int[] arreglo)
        {
            // Considerar un valor (A[-1].clave = -∞)
            // cuyo valor de clave sea menor a todos los valores del arreglo
            int min = -9999;
            int j;
            // Realizar n pasadas
            for (int i = 1; i < arreglo.Length; i++)
            {
                // En cada recorrido ubicar el i-ésimo elemento en su posición ordenada
                j = i;
                while (arreglo[j] < arreglo[j - 1])
                {
                    intercambiar(ref arreglo[j], ref arreglo[j - 1]);
                    // Comparar con el valor mínimo
                    // Consideramos esta condición pues en arreglos de
                    // C# no se considera indices menores a 0.
                    if (j<=0)
                    {
                        if (arreglo[j] < min)
                        {
                            intercambiar(ref arreglo[j], ref min);
                        }
                        break; // abandonar la iteración 
                    }
                    j = j - 1;
                }
            }
        }

        /*
         * Método para peermutar los valores de dos variables enteras.
         */
        static void intercambiar(ref int a, ref int b)
        {
            // intercambia(A[j],A[j-1])
            int temp = a;
            a = b;
            b = temp;
        }

3) Implementar el algoritmo de ordenación por Selección.

         /*
         * Método para implementar la Clasificación u ordenación por Selección.
         */

        static void clasificacionPorSeleccion(ref int[] arreglo)
        {
            int indice_menor;
            int clave_menor;
            for (int i = 0; i < arreglo.Length-1; i++)
            {
                // Elegir el menor entre A[i], ..., A[n] e intercambiarlo con A[i]
                indice_menor = i;
                clave_menor = arreglo[i];
                for (int j = i; j < arreglo.Length; j++)
                {
                    // Comparar la clave con la actual clave menor
                    if (arreglo[j] < clave_menor)
                    {
                        clave_menor = arreglo[j];
                        indice_menor = j;
                    }
                }
                intercambiar(ref arreglo[i], ref arreglo[indice_menor]);
            }
        }


IV) TAREA:
  1. Evaluar gráficamente la complejidad de tiempo de los métodos.
  2. Considere dentro de la evaluación, el caso de que los valores del arreglo ya estén ordenados, o en orden inverso.
  3. Implemente el método de clasificación Shellsort.

V) REFERENCIAS BIBLIOGRÁFICAS
  • Estructura de datos y algoritmos, Alfred V. Aho, John E. Hopcroft, Jefrey D. Ullman.
Comments