• Author / Uploaded
• Francisco Cares

Citation preview

Universidad de Santiago de Chile Ingeniería Civil en Electricidad Laboratorio de Computación

Algoritmo de ordenamiento Shell Sort

Cristóbal Fica

Integrantes:

Francisco Cares Michael Vargas

Página

1

Ayudante:

25 de octubre de 2013

Universidad de Santiago de Chile Ingeniería Civil en Electricidad Laboratorio de Computación

Contenido Algoritmo de ordenamiento Shell Sort ........................................................................................ 1 Introducción .................................................................................................................................. 3 Shell Sort ....................................................................................................................................... 3 Memoria .................................................................................................................................... 4 Pseudocódigo ................................................................................................................................ 5 Código en Matlab .......................................................................................................................... 6 Aplicación y alcances ..................................................................................................................... 6 Conclusión ..................................................................................................................................... 7

Página

2

Bibliografía .................................................................................................................................... 7

25 de octubre de 2013

Universidad de Santiago de Chile Ingeniería Civil en Electricidad Laboratorio de Computación

Introducción

El ordenamiento Shell (Shell Sort en inglés) es un algoritmo de ordenamiento, denominado así en honor a su inventor Donald Shell, que lo publicó en 1959. Algunos libros de texto y referencias antiguas le llaman ordenación "Shell-Metzner" por Marlene Metzner Norton, pero según Metzner, "No tengo nada que ver con el algoritmo de ordenamiento, y mi nombre nunca debe adjuntarse a éste.". El Shell Sort es una mejora del algoritmo de ordenamiento por inserción (Insertsort).

Shell Sort

La forma en que trabaja Shell Sort es la siguiente: 

Organizar la secuencia de datos en una matriz de dos dimensiones



Ordenar las columnas de la matriz

El efecto producido es una secuencia de datos que se clasifica parcialmente. El proceso anterior se repite, pero cada vez con una gama más estrecha, es decir, con un menor número de columnas. En el último paso, la matriz consta de una sola columna. En cada paso, el ordenamiento de la secuencia se incrementa, hasta que en el último paso se encuentre completamente ordenado. Sin embargo, el número de operaciones necesarias en cada paso de clasificación es limitado, debido al pre-ordenamiento de la secuencia obtenida en los pasos

Página

3

anteriores.

25 de octubre de 2013

Universidad de Santiago de Chile Ingeniería Civil en Electricidad Laboratorio de Computación

Memoria ShellSort trabaja en la memoria principal, por lo que se asume que el tiempo de acceso es el mismo para cualquier elemento (acceso aleatorio). Ejemplo: Supongamos que [3 7 9 0 5 1 8 6 4 2 0 6 1 5 7 3 4 9 8 2] sea la secuencia de datos para ser resuelto. En primer lugar, está dispuesto en una matriz con 7 columnas (izquierda), a continuación, se ordenan las columnas (a la derecha): 3 7 9 0 5 1 6

3 3 2 0 5 1 5

8 4 2 0 6 1 5

7 4 4 0 6 1 6

7 3 4 9 8 2

8 7 9 9 8 2

Los elementos de datos 8 y 9 ahora ya han llegado al final de la secuencia, sino un elemento pequeño (2) también sigue ahí. En el siguiente paso, la secuencia está dispuesta en 3 columnas, que se ordenan de nuevo: 3 3 2

0 0 1

0 5 1

1 2 2

5 7 4

3 3 4

4 0 6

4 5 6

1 6 8

5 6 8

7 9 9

7 7 9

8 2

8 9 Ahora la secuencia está casi completamente solucionada. Cuando la organización de

una columna en el último paso, que es sólo un 6, un 8 y un 9 tienen que trasladarse a su

Página

4

posición correcta.

25 de octubre de 2013

Universidad de Santiago de Chile Ingeniería Civil en Electricidad Laboratorio de Computación

Pseudocódigo

1) Algoritmo ShellSort(lista) 2) Pre: lista≠0 3) Post: lista tiene un ordenamiento en los valores de forma ascendente 4) incremento←lista. Contador/2 5) While incremento≠0 6)

Actual←incremento

7)

While actualinc && data(j-inc)>tmp) data(j) = data(j-inc); j = j-inc; end data(j) = tmp; end inc = cast(floor(double(inc) /2),'int16'); end dataOut = data;

Aplicación y alcances Aplicaciones evidentes: 

Mostrar los ficheros de un directorio.



Mostrar un listado ordenado del contenido de una base de datos (ej.: listado alfabético).



Ordenar los resultados de una búsqueda en Internet (ej.: Google, PageRank).

Problemas que resultan más sencillos de resolver con de Solver de ordenamiento: Realizar una búsqueda (p.ej... búsqueda binaria).



Encontrar la mediana.



Encontrar el par más cercano.



Identificar / “outliers” / anomalías



Detectar duplicados.

Página

6



25 de octubre de 2013

Universidad de Santiago de Chile Ingeniería Civil en Electricidad Laboratorio de Computación

Conclusión

El análisis de su eficiencia es un problema complicado y aun no resuelto, puesto que, ninguna persona ha sido capaz de establecer la mejor secuencia de incrementos cuando N es muy grande. De modo que Shell Sort no es el algoritmo más eficiente para ordenar arreglos comparándolo con la complejidad de los algoritmos Quicksort, Mergesort y Heapsort, sin embargo, es un algoritmo mucho más fácil de programar. Su simplicidad radica en que deriva del algoritmo más simple para ordenar, Insert Sort.

Bibliografía 

Enciclopedia libre, Wikipedia. Modificada por última vez el 8 agosto, 2013.

http://es.wikipedia.org/wiki/Ordenamiento_Shell 

Algoritmos de Ordenamiento, Fernando A. Lagos B.

http://blog.zerial.org/ficheros/Informe_Ordenamiento.pdf 

Fachhochschule Flensburg, Universidad de Ciencias Aplicadas, Alemania. Publicado el 29 enero, 1998.

Página

7

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm

25 de octubre de 2013