Fianzas, riesgo

Informe de Tarea 2: Shellsort

Algoritmos y Estructuras de Datos

[pic 1]

Introducción

El objetivo de este informe es explicar el método de ordenación Shellsort y estudiar de forma experimental el tiempo que al método le tarda ordenar n elementos.
El método de ordenamiento Shellsort se basa en la idea de “h-ordenar” un arreglo, donde h es entero mayor o igual 1.

Para h-ordenar un arreglo, se aplica ordenación por inserción a cada subconjunto de elementos que se obtiene al tomar aquellos elementos que están a distancia h dentro del arreglo a ordenar. Se realizan h-ordenamientos sucesivos de forma que h sea decreciente y el ultimo sea igual a 1, donde con esto se garantiza que el arreglo final quede ordenado, pues 1-ordenar es equivalente a ordenar, pero los h-ordenamientos previos aceleran el proceso, con lo que se logra un método más eficiente.

Se programó el método Shellsort y se probó con diferentes sucesiones, estas fueron: la sucesión <1>, la sucesión de los 2k-1 (decreciente y tal que el primer término es el más cercano a n), y la sucesión que obtiene con <1,4,10,23,57,132,301,701> y los siguientes valores de la sucesión se calculan con la formula hk=⌊2,25hk−1⌋ hasta llegar al más cercano a n.
Se realizaron experimentos para medir cuánto tardan dichos métodos para arreglos de diferentes tamaños y se calculó el número de comparaciones que utilizan como indicador de eficiencia del algoritmo.

Finalmente se graficaron las eficiencias en promedio de cada método en function de n.

Implementación

El primero de los métodos implementados la secuencia <1>, es decir solamente1-ordenar. Para ello el algoritmo implementado fue el siguiente:

int c=1;

long contador1=0;

Donde c es el indicador que apunta al objeto que se está comparando, y contador1 es el número de comparaciones que realiza el método.

while (c

        double t=lista1[c];

        for (int j=c; j>0 && lista1[j-1]>t; --j){

En este caso, j indica con quién se está comparando el índice c, y el método “for” busca entre los que se encuentran ordenados si existe algún valor mayor que “c” para reemplazarlo por ese otro valor.

                lista1[j]=lista1[j-1];

                lista1[j]=t;

                contador1++;

        }

        ++c;

        contador1++;        

 }

El segundo método a implementar es el con salto igual a 2k-1, desde el valor más cercano a n. Para implementarlo el algoritmo utilizado fue el siguiente:

int[] salto_2=new int[k];

Se genera primero una lísta con los saltos necesarios

for (int i=0, j=k; i

        salto_2[i]=(int) (Math.pow(2,j)-1);

        }

Se guarda el número de comparaciones con este método en “contador2”

long contador2=0;

double aux2;

for(int i=0;i        

Se toma cada número de la sucesión ordenada de mayor a menor, hasta llegar a uno

    for(int j=0;j

Toma el primer número de la lista (avanzando un intervalo determinado por la secuencia) y lo compara compara con el número que está a una distancia igual al número correspondiente a la secuencia más alejado del primero

        for(int k2=(j+salto_2[i]);k2

Cambia posiciones entre los numeros a comparar dependiendo si es mayor o menor

            if(lista2[k2]

                aux2=lista2[j];

                lista2[j]=lista2[k2];

                lista2[k2]=aux2;

                                contador2++;

                        }

                        contador2++;

                }

        contador2++;

        }

contador2++;        

}

Para el tercer método se utiliza un salto igual a 2.25*h_k-1, primero se cuenta hasta dónde es necesario llegar.

int cont=7;

for (double h=701; h<=lista3.length; h=2.25*h){

        cont++;

}

long contador3=0; //número de comparaciones con metodo 3

double[] salto_3=new double[cont+1];

generaremos una lista con los saltos necesarios

salto_3[cont]=1;

salto_3[cont-1]=4;

salto_3[cont-2]=10;

salto_3[cont-3]=23;

salto_3[cont-4]=57;

salto_3[cont-5]=132;

salto_3[cont-6]=301;

salto_3[cont-7]=701;

for (int i=cont-8; i>=0; i--){

        salto_3[i]=2.25*salto_3[i+1];

}

int aux3;

for(int i=0;i

                                    for(int j=0;jToma el primer número de la lista (va avanzando un intervalo determinado por la secuencia) y lo compara compara con el número que esta a una distancia igual al número correspondiente a la secuencia más alejado del primero

...