Método de ordenamiento Shell

0
836

Descargar Solución OrdenamientoMetodoShell.zip

Fue nombrado Ordenamiento de disminución incremental 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 incremento.

Después de que los primeros K subgrupos han sido ordenados (generalmente utilizando INSERCION DIRECTA), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.

Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado.

Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.

“Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos.”

Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.

El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1.

Ejemplo:

Para el arreglo a = [6, 1, 5, 2, 3, 4, 0]

Tenemos el siguiente recorrido:

Recorrido Salto Lista Ordenada Intercambio
1 3 2,1,4,0,3,5,6 (6,2),(5,4),(6,0)
2 3 0,1,4,2,3,5,6 (2,0)
3 3 0,1,4,2,3,5,6 Ninguno
4 1 0,1,2,3,4,5,6 (4,2),(4,3)
5 1 0,1,2,3,4,5,6 Ninguno

Descargar Solución OrdenamientoMetodoShell.zip

Dejar respuesta

Please enter your comment!
Please enter your name here

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.