8.5. Ordenación Shell - Definición y Algoritmo

El Ordenamiento Shell, también conocido como Shellsort, es un algoritmo de ordenación que mejora la eficiencia del ordenamiento por inserción al comparar y mover elementos que están lejos entre sí. Fue desarrollado por Donald Shell en 1959. Shellsort es más eficiente que los algoritmos simples como el ordenamiento por burbuja, selección o inserción, especialmente para listas grandes.

Definición

Shellsort funciona dividiendo la lista en sublistas de elementos separados por un intervalo determinado y aplicando el ordenamiento por inserción a cada sublista. A medida que el algoritmo avanza, el intervalo se reduce hasta que el intervalo es 1, momento en el cual se aplica una última pasada de ordenamiento por inserción. Este método reduce el número de intercambios necesarios al mover elementos más cercanos a su posición final desde el principio del algoritmo.

Algoritmo

  1. Inicialización: Dividir la lista en sublistas de elementos distantes utilizando un intervalo inicial.
  2. Ordenamiento de sublistas: Aplicar el ordenamiento por inserción a cada sublista.
  3. Reducción del intervalo: Reducir el intervalo y repetir el proceso hasta que el intervalo sea 1.
  4. Ordenamiento final: Aplicar el ordenamiento por inserción a la lista completa.

Pseudocódigo

procedure shellSort(A: list of sortable items)
    n = length(A)
    gap = n // 2
    while gap > 0 do
        for i = gap to n - 1 do
            temp = A[i]
            j = i
            while j >= gap and A[j - gap] > temp do
                A[j] = A[j - gap]
                j = j - gap
            end while
            A[j] = temp
        end for
        gap = gap // 2
    end while
end procedure

Descripción del Pseudocódigo

  1. Inicialización: El intervalo (gap) se inicializa como la mitad del tamaño de la lista.
  2. Bucle principal: Mientras el intervalo sea mayor que 0, se continúa el proceso.
  3. Bucle de inserción: Para cada elemento de la lista a partir del índice igual al intervalo hasta el final de la lista, se realiza el ordenamiento por inserción:
    • El elemento actual se almacena en una variable temporal (temp).
    • Se compara el elemento actual con el elemento gap posiciones atrás. Si el elemento anterior es mayor, se mueve hacia adelante.
    • Este proceso se repite hasta que se encuentre la posición correcta para el elemento temporal.
  4. Reducción del intervalo: El intervalo se divide por 2 y se repite el proceso.