Algoritmo de Ordenamiento Shell - Historial de revisiones

Cinformpri jc en 18:28 17 oct 2013

2013-10-17T18:28:51Z

Cinformpri jc: /* Ver además */

2013-10-17T18:25:29Z

‎Ver además

Midel: /* Vease también */

2012-01-19T19:15:06Z

‎Vease también

Candelaria2 jc en 13:28 20 ago 2011

2011-08-20T13:28:34Z

Mostrar los cambios

Cinformiju jc en 15:53 17 ago 2011

2011-08-17T15:53:01Z

Manuel jc.manzanillo1: /* Secuencia de espacios */

2011-08-16T19:09:23Z

‎Secuencia de espacios

Manuel jc.manzanillo1: /* Vease también */

2011-08-16T19:06:38Z

‎Vease también

Manuel jc.manzanillo1: /* Vease también */

2011-08-16T19:05:12Z

‎Vease también

Manuel jc.manzanillo1: /* Vease también */

2011-08-16T19:04:10Z

‎Vease también

Manuel jc.manzanillo1: /* Vease también */

2011-08-16T19:02:24Z

‎Vease también

← Revisión anterior		Revisión del 18:28 17 oct 2013
Línea 1:		Línea 1:
−	{{Definición\|Nombre=Algoritmo de ordenamiento. Shell\|imagen=~~Sorting_quicksort_~~.~~JPG~~\|concepto=Algoritmo que pone elementos de una lista o un vector, en una secuencia dada por una relación de orden, siendo una generalización del ordenamiento por inserción}}	+	{{Definición\|Nombre=Algoritmo de ordenamiento. Shell\|imagen=Algoritmoordenamientoshell.jpeg‎ \|concepto=Algoritmo que pone elementos de una lista o un vector, en una secuencia dada por una relación de orden, siendo una generalización del ordenamiento por inserción}}

	'''Algoritmo de ordenamiento Shell:''' El método se denomina así en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso, aunque 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 [[algoritmo]]s simples pero peor que el óptimo O(n log n).		'''Algoritmo de ordenamiento Shell:''' El método se denomina así en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso, aunque 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 [[algoritmo]]s simples pero peor que el óptimo O(n log n).

@@ Línea 127: / Línea 127: @@
   </source>
-==Ver además==
+==Véase también==
 *[[Algoritmo de  ordenamiento]]
 *[[Algoritmo de búsqueda]]

@@ Línea 127: / Línea 127: @@
   </source>
-== Vease también ==
+==Ver además==
+*[[Algoritmo de  ordenamiento]]
-*[[Algoritmo de ordenamiento]].
+*[[Algoritmo de búsqueda]]
-*[[Ordenamiento de burbuja]]
+*[[Algoritmo de Kruskal]]
-*[[Algoritmos de clasificación no supervisada]]
+*[[Algoritmo  de Euclides]]
-*[[Algoritmos jerárquicos]]
+*[[Algoritmo de Prim]]
-*[[Algoritmos matemáticos]]
+*[[Algoritmo de Boruvka]]
 == Fuentes ==

@@ Línea 95: / Línea 95: @@
 *[[Algoritmo de ordenamiento]].
 *[[Ordenamiento de burbuja]]
+*[[Algoritmos de clasificación no supervisada]]
 == Fuentes ==
 *Aprenda C/C++.

@@ Línea 17: / Línea 17: @@
 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).
 == 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'' 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.
 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.
 == Análisis del Costo Computacional ==
 Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución. 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(nlog2n), y posiblemente mejores tiempos de ejecución no comprobados. La existencia de una implementación O(nlogn) en el peor caso del Shell sort permanece como una pregunta por resolver.

@@ Línea 92: / Línea 92: @@
 == Vease también ==
-*[[Algoritmos de ordenamiento]].
+*[[Algoritmo de ordenamiento]].
 *[[Algoritmos de ordenamiento. Burbuja]]