Ordenamiento Shell

Ordenamiento Shell

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. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(n log2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.

El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:

  1. El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
  2. El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.

El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

Contenido

Ejemplo

Considere un valor pequeño que está inicialmente almacenado en el final del vector. Usando un ordenamiento O(n2) como el ordenamiento de burbuja o el ordenamiento por inserción, tomará aproximadamente n comparaciones e intercambios para mover este valor hacia el otro extremo del vector. El Shell sort primero mueve los valores usando tamaños de espacio gigantes, de manera que un valor pequeño se moverá bastantes posiciones hacia su posición final, con sólo unas pocas comparaciones e intercambios.

Uno puede visualizar el algoritmo Shell sort de la siguiente manera: coloque la lista en una tabla y ordene las columnas (usando un ordenamiento por inserción). Repita este proceso, cada vez con un número menor de columnas más largas. Al final, la tabla tiene sólo una columna. Mientras que transformar la lista en una tabla hace más fácil visualizarlo, el algoritmo propiamente hace su ordenamiento en contexto (incrementando el índice por el tamaño de paso, esto es usando i += tamaño_de_paso en vez de i++).

Por ejemplo, considere una lista de números como [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 8, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas. Esto quedaría así:

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

Entonces ordenamos cada columna, lo que nos da

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

Cuando lo leemos de nuevo como una única lista de números, obtenemos [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. Aquí, el 10 que estaba en el extremo final, se ha movido hasta el extremo inicial. Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de 3 posiciones, y después un ordenamiento con un espacio de 1 posición (ordenamiento por inserción simple).

El Shell sort lleva este nombre 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." [1]

Secuencia de espacios

La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la secuencia de espacios. Continua para realizar un ordenamiento por inserción con espacio para cada número en la secuencia, hasta que termina con un espacio de 1. Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada.

La secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar 1. Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción, se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento O(n2) del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice impar.

Quizás la propiedad más crucial del Shell sort es que los elementos permanecen k-ordenados incluso mientras el espacio disminuye. Se dice que un vector dividido en k subvectores esta k-ordenado si cada uno de esos subvectores esta ordenado en caso de considerarlo aislado. Por ejemplo, si una lista fue 5-ordenada y después 3-ordenada, la lista está ahora no sólo 3-ordenada, sino tanto 5-ordenada como 3-ordenada. Si esto no fuera cierto, el algoritmo desharía el trabajo que había hecho en iteraciones previas, y no conseguiría un tiempo de ejecución tan bajo.

Dependiendo de la elección de la secuencia de espacios, Shell sort tiene un tiempo de ejecución en el peor caso de O(n2) (usando los incrementos de Shell que comienzan con 1/2 del tamaño del vector y se dividen por 2 cada vez), O(n3 / 2) (usando los incrementos de Hibbard de 2k − 1), O(n4 / 3) (usando los incrementos de Sedgewick de 9(4i) − 9(2i) + 1, o 4i + 1 + 3(2i) + 1), o O(nlog 2n), y posiblemente mejores tiempos de ejecución no comprobados. La existencia de una implementación O(nlog n) en el peor caso del Shell sort permanece como una pregunta por resolver.

Referencias

  • Weiss, Mark Allen (2002). Data Structures & Problem Solving using Java. Addison Wesley. ISBN 0-201-74835-5. 
  • Pratt, V (1979). Shellsort and sorting networks (Outstanding dissertations in the computer sciences). Garland. ISBN 0-8240-4406-1.  (Esto fue originalmente presentado como la tesis doctoral del autor en la Universidad de Stanford en 1971)

Enlaces externos


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Algoritmo de ordenamiento — Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote. En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por …   Wikipedia Español

  • Ordenación Shell Sort — El Shell Sort es un ordenamiento de disminución incremental, nombrado así debido a su inventor Donald Shell. Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado… …   Enciclopedia Universal

  • Comb sort — En ciencias de la computación, el comb sort es un algoritmo de ordenamiento relativamente simple diseñado por Wlodzimierz Dobosiewicz en 1980. Posteriormente fue redescubierto y popularizado por Stephen Lacey y Richard Box en un artículo… …   Wikipedia Español

  • Orden (desambiguación) — Orden puede adqurir varios significados en diferentes disciplinas. Puede referirse a: Contenido 1 Teoría de sistemas 2 Criterios de ordenación 3 Significados en diferentes ciencias 3.1 …   Wikipedia Español

  • Historia de Salvador Mazza (Salta) — Este artículo o sección sobre historia y sociedad necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 12 de julio de 2009. También… …   Wikipedia Español

  • Historia de Cabimas — Este artículo o sección sobre historia necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 4 de enero de 2008. También puedes ayudar… …   Wikipedia Español

  • Mene Grande — Coordenadas: 9°49′56″N 70°55′26″O / 9.83222, 70.92389 Mene Grande es una población del municipio Baralt en el estado Zulia en la …   Wikipedia Español

  • Nanotubo — Nanotubos de carbono. Representación de l …   Wikipedia Español

  • Sierra de la Macarena — Sierra de la Macarena …   Wikipedia Español

  • Teoría ácido-base duro-blando — La teoría ácido base duro blando, también conocida como teoría ABDB, concepto ácido base de Pearson, teoría HSAB (por sus siglas en inglés) es un modelo ampliamente utilizado en química para explicar la estabilidad de los compuestos y mecanismos… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”