En este post vamos a aprender que es el método de ordenación shell sort y en que casos determinados se utiliza y porque.
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 rendimiento de O(nlog2 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.
En otras palabras, es un metodo de ordenamiento que permite recorrer el array que tengamos(no importa de que tamaño) en cierta distancia dependiendo del tamaño del array.
EJEMPLO
Ordenar el siguietne array de 10 posiciones:
[16][72][23][9][1][56][12][99][40][7]
Siguiendo la formula K=N/2; siendo k la distancia que vamos a tener para comparar un elemento con otro dentro del array y N el total de elementos del array, podremos saber que distancia hay que recorrer en el array para empezar a comparar:
[16]--------5--------[56]
[72][23][9][1] [12][99][40][7] K=10/2
K=5
Una vez hecho esto la comparacion puede hacerse de dos formas:
-Comparar si el primer elemento es mayor al segundo elemento (16>56)
-Comparar si el segundo elemento es menor al primer elemento (56<16)
Si la comparación se cumple de cualquiera de las dos formas, entonces los elementos se invierten, en este caso, como la condición no se cumple se deja tal como esta, acto seguido se comparan los elementos que le siguen 1 espacio:
[72]------5---------[12]
[16] [23][9][1][56] [99][40][7] (72>16)
(16<72)
Como la comparacion se cumple se invierten las posiciones:
[16][12][23][9][1][56][72][99][40][7]
Nuevamente el proceso debe repetirse hasta que se recorra todo el array. Una vez que eso pase lo siguiente sera dividir el valor de K nuevamente entre 2 y continuar el proceso anterior K=5/2=2.5=2,pero esta vez con la distancia de elementos de 2:
[16] -2- [23]
[12] [9][1][56][72][99][40][7]
Una vez recorrido el array nos quedara los siguiente:
[16][9][1][12][23][56][40][7][72][99]
Por ultimo, dividimos K nuevamente entre 2 y nos dará K=2/2=1, donde ya compararemos posición por posición, pero si la comparación se cumple se comparara una vez mas con la posición anterior el:
[16][9]
[1][12][23][56][40][7][72][99]
[16][1]
[9] [12][23][56][40][7][72][99]
[9][1]
[16][12][23][56][40][7][72][99]
[1][9][16][12][23][56][40][7][72][99]
Luego de hacer las comparaciones finalemtne nos quedara nuestro array ordenado:
[1][7][9][12][16][23][40][56][72][99]
COMO USAR SHELL SORT EN JAVA
Para aprender a programar el método de ordenamiento shell en java pueden ver el siguiente vídeo y/0 también pueden descargar el programa que he hecho por mi cuenta:
Descargar programa: shell sort
Sin mas que decir espero que les haya servido.
la información utilizada de las siguientes paginas:
- GÓMEZ, Daniel Ricardo . y JORDAN, Jorge Eduardo . Ordenamiento Shell. [EN LINEA]. Web. jueves, 21 de mayo de 2009. [Citado en 29 de Septiembre de 2015]. Disponible en internet: <http://estructuradedatosdrgjej.blogspot.com.co/2009/05/ordenamiento-shell.html>
- SANCHEZ REYES, Jonathan Dayessi . Ordenamiento Shell En Java. [EN LINEA]. Web. 13 de octubre 2014. [Citado en 30 de Septiembre de 2015]. Disponible en internet: <https://youtu.be/g_8b6k7gsi4>http://estructuradedatosdrgjej.blogspot.com.co/2015/09/ordenamiento-shell.html
