Shell Sort

Shell Sort

Objetivos:

Explicar el funcionamiento del algoritmo de ordenación Shell

Mostrar distintos algoritmos de ordenamiento, comparando su eficiencia en tiempo de ejecución.

Antecedentes:

El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald Shell ; y parte de un algoritmo de ordenacion interna muy sencilla pero muy ingeniosa, basado en comparaciones e intercambios, y con resultados radicalmente mejores que los que se pueden obtener con el metodo de la burbuja, el de selección directa o el de inserccion directa.

Ventajas:

Reduce el tiempo de ejecución, lo cual es de mucha importancia en el medio sistematico

Desventajas:

No es un algoritmo en-linea; esto quiere decir que no se puede trabajar a medida que va recibiendo los datos de entrada; o sea que trabaja despues de ingresar todos los datos

Caracteristicas:

Se trata de un algoritmo de ordenación interna.

Se basa en comparaciones e intercambios

La k-ordenacion:

Shellsort crea sub-arreglos, pero no de forma definitiva; en otras palabras, este ordenamiento se realiza a través de K saltos: Donde K= # elementos / 2, partiendo desde la casilla 0, pero realizando K saltos hasta el siguiente elementos, haciendo esto hasta terminar el recorrido y proceder a ordenar los elementos seleccionados “el sub-arreglo”; Despues de ello K toma otro valor, K=K/2 y esto se realiza hasta que K=1, lo cual nos dice que se ha ordenado los elementos en un 100%.

Desarrollo:

procedimiento ShellSort( v []entero,tamaño entero)

{

Variables int salto =0, sw =0, aux =0,e =0;

salto = tamaño/2;

mientras(salto > 0)

{

sw =1;

mientras(sw!=0)

{

sw=0;

e=1;

mientras(e<=(tamaño-salto))

{

si(v[e-1]>v[(e-1)+salto])

{

aux = v[(e-1)+salto];

v[(e-1)+salto] = v[e-1];

v[e-1] = aux;

sw =1;

}fin_si

e = e +1;

}fin_mientras

}fin_mientras

salto = salto /2;

}fin_mientras

}fin_procedimiento

Conclusiones:

Si bien Shellsort no es el algoritmo más eficiente para ordenar arreglos, comparado con la complejidad O(n *ln(n)) de los algoritmos Quicksort, Bubblesort y Heapsort, es un algoritmo mucho más fácil de programar

...