Ordenamiento Shell

El ordenamiento Shell (Shell Sort) es una versión eficiente y mejorada del ordenamiento por inserción, propuesta por Donald Shell en 1959.

La idea central del ordenamiento Shell esdividir la lista original en múltiples subsecuencias, aplicar primero el ordenamiento por inserción a cada subsecuencia, luego reducir gradualmente el intervalo entre subsecuencias y, finalmente, realizar un ordenamiento por inserción estándar sobre toda la lista.Este método permite que los elementos se muevan en grandes saltos, eliminando así una gran cantidad de inversiones en las primeras etapas y mejorando significativamente la eficiencia del ordenamiento.

Imagina ordenar una baraja de cartas desordenada. El ordenamiento por inserción es como tomar las cartas una por una e insertarlas en la posición correcta de la pila ya ordenada en la mano. El ordenamiento Shell, en cambio, es como primero extraer una carta cada varias para formar una pequeña pila y ordenarla, luego reducir el intervalo de extracción y repetir el proceso. Cuando el intervalo se reduce a 1, se convierte en un ordenamiento por inserción estándar, pero para entonces toda la secuencia ya está casi ordenada, por lo que el ordenamiento por inserción final será muy rápido.

Principio de funcionamiento

La clave del ordenamiento Shell radica en un concepto llamadosecuencia de incrementosLa secuencia de incrementos determina el intervalo para dividir las subsecuencias en cada pasada. El algoritmo realiza varias rondas de ordenamiento sobre la lista siguiendo una secuencia de incrementos que disminuye gradualmente.

Pasos del algoritmo

  1. Seleccionar la secuencia de incrementos: Determinar una secuencia de enteros de mayor a menor; el último incremento debe ser 1. El incremento inicial más común es la mitad de la longitud del arreglo, y luego se reduce a la mitad sucesivamente.
  2. Agrupar por incremento: Para el incremento actualgap, se divide toda la lista engapsubsecuencias. Cada subsecuencia está formada por todos los elementos separados porgapese intervalo.
  3. Aplicar el ordenamiento por inserción a las subsecuencias: Aplicar el ordenamiento por inserción a cada subsecuencia por separado.
  4. Reducir el incremento: Obtener un nuevo incremento más pequeño y repetir los pasos 2 y 3.
  5. Ordenamiento final: Cuando el incremento se reduce a 1, se realiza un ordenamiento por inserción estándar sobre toda la lista; en ese momento la lista ya está casi ordenada y el ordenamiento se completa rápidamente.

Notas de aplicación

La complejidad temporal del ordenamiento Shell esO(n^(1.3-2)), y la complejidad espacial es de orden constanteO(1). El ordenamiento Shell no es más rápido que el algoritmo de ordenamiento rápido (quicksort)O(n(logn)); por lo tanto, se comporta bien en tamaños medianos, pero no es la opción óptima para ordenar conjuntos de datos muy grandes; en resumen, es mucho más rápido que los algoritmos deO(n^2 )complejidad común.

Ilustración del proceso

El propósito del ordenamiento Shell es mejorar el ordenamiento por inserción para acelerar la velocidad: intercambia elementos no adyacentes para ordenar localmente el arreglo y, finalmente, usa el ordenamiento por inserción para ordenar el arreglo parcialmente ordenado.

Aquí elegimos el incrementogap=length/2, reduciendo el incrementogap = gap/2mediante el método, y usamos la secuencia{n/2,(n/2)/2...1}para representarlo.

Como se muestra en el ejemplo de la figura:

(1) Primera pasada con el incremento inicialgap = length/2 = 4

(2) Segunda pasada, el incremento se reduce a 2

(3) Tercera pasada, el incremento se reduce a 1, obteniendo el resultado final ordenado.

Código de ejemplo en Java

Descargar el paquete de código fuente:Download

El bucle más interno es en realidad el ordenamiento por inserción:

Código del archivo ShellSort.java:

public class ShellSort {
    //Inicio del código central---
    public static void sort(Comparable[] arr) {
        int j;
        for (int gap = arr.length / 2; gap >  0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                Comparable tmp = arr[i];
                for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tmp;
            }
        }
    }
    //Fin del código central---
    public static void main(String[] args) {

        int N = 2000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 10);
        ShellSort.sort(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }
}

Implementación del algoritmo en Python

Usaremos Python para implementar el ordenamiento Shell y adoptaremos la configuración de incrementos más común (la secuencia original de Shell):gap = n // 2, y continuamos dividiendogapentre 2, hasta quegapsea 1.

Ejemplo

def shell_sort(arr):
    """
Ordena la lista en orden ascendente in situ utilizando el algoritmo de ordenamiento Shell.
   
Parámetros:
arr (list): la lista a ordenar.
   
Retorna:
list: la lista ordenada (modificada in situ, también se retorna).
    """
    n = len(arr)
    # El incremento inicial gap se establece como la mitad de la longitud del arreglo
    gap = n // 2
   
    # Bucle hasta que gap se reduzca a 0
    while gap > 0:
        # Comenzando desde gap, se aplica "ordenamiento por inserción" a cada elemento
        # Nota: aquí i va de gap a n-1, recorriendo todos los elementos
        for i in range(gap, n):
            # Guardar arr[i] en la variable temporal temp
            temp = arr[i]
            j = i
            # Aplicar ordenamiento por inserción a la subsecuencia correspondiente al gap actual
            # Si el elemento anterior en la misma subsecuencia es mayor que temp, desplazarlo hacia la derecha
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            # Insertar temp en la posición correcta
            arr[j] = temp
        # Reducir el incremento, por ejemplo, reducir gap a la mitad
        gap //= 2
   
    return arr

# Código de prueba
if __name__ == "__main__":
    # Datos de prueba 1: aleatorio desordenado
    test_array = [8, 3, 5, 1, 4, 2, 7, 6]
    print("Antes de ordenar:", test_array)
    sorted_array = shell_sort(test_array.copy()) # Usar copy para evitar modificar el arreglo original
    print("Después de ordenar:", sorted_array)
   
    # Datos de prueba 2: con elementos repetidos
    test_array2 = [5, 2, 9, 5, 2, 3, 5]
    print("\n"Antes de ordenar:", test_array2)
    print("Después de ordenar:", shell_sort(test_array2.copy()))
   
    # Datos de prueba 3: arreglo en orden inverso
    test_array3 = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
    print("\n"Antes de ordenar:", test_array3)
    print("Después de ordenar:", shell_sort(test_array3.copy()))

Análisis del código:

  1. def shell_sort(arr):Definir la función de ordenamiento Shell.
  2. n = len(arr)Obtener la longitud del arreglo.
  3. gap = n // 2Inicializar el incremento. Este es el punto de partida más clásico de la secuencia de incrementos del ordenamiento Shell.
  4. while gap > 0:Bucle externo: controla que el incremento disminuya gradualmente hasta 0 (después de ejecutarse con el valor 1,gap //= 2se convierte en 0 y sale del bucle).
  5. for i in range(gap, n):Bucle interno. Desde el índicegapse comienza a recorrer.iSeñala el elemento actual que se va a insertar. Nota: este bucle maneja hábilmente a la vez todas las subsecuencias que tienengapcomo intervalo.
  6. temp = arr[i]yj = i: guarda el valor del elemento actual y usajpara registrar la posición donde debe insertarse en la subsecuencia actual.
  7. while j >= gap and arr[j - gap] > temp:Este es el núcleo del ordenamiento por inserción. Dentro de la misma subsecuencia (mediante el índicej - gapse accede al elemento anterior), si el elemento anterior es mayor quetemp, se desplaza el elemento anteriorgapposiciones hacia la derecha.
  8. arr[j] = temp: el valor guardadotempse inserta en la posición correcta.
  9. gap //= 2: después de una ronda de ordenamiento, se reduce el incremento a la mitad para realizar la siguiente ronda de ordenamiento más fino.
  10. return arr: retorna el arreglo ordenado.

Selección de la secuencia de incrementos

La elección de la secuencia de incrementos afecta directamente el rendimiento del ordenamiento Shell. Arriba hemos usado la secuencia original de Shell (n/2, n/4, ..., 1), pero no es la óptima. A continuación se presentan varias secuencias de incrementos comunes:

Nombre de la secuencia Fórmula de generación Características y complejidad
Secuencia original de Shell $gap = \lfloor \frac{n}{2} \rfloor, gap = \lfloor \frac{gap}{2} \rfloor...$ Implementación sencilla; la complejidad temporal en el peor caso es $O(n^2)$.
Secuencia de Hibbard $1, 3, 7, 15, ..., 2^k - 1$ La complejidad temporal en el peor caso puede mejorarse a $O(n^{3/2})$.
Secuencia de Knuth $1, 4, 13, 40, ..., (3^k - 1) / 2$ (menor que n) La complejidad temporal promedio es aproximadamente $O(n^{1.25})$, de uso común en la práctica.
Secuencia de Sedgewick $1, 5, 19, 41, 109, ...$ (combina $9 \times 4^k - 9 \times 2^k + 1$ y $4^k - 3 \times 2^k + 1$) Es una de las mejores secuencias conocidas; la complejidad en el peor caso puede alcanzar $O(n^{4/3})$.

Ejemplo de implementación con la secuencia de Knuth

Ejemplo

def shell_sort_knuth(arr):
    n = len(arr)
    # Generar la secuencia de incrementos de Knuth: 1, 4, 13, 40, 121, ...
    gap = 1
    while gap < n // 3:
        gap = 3 * gap + 1  # Generar el incremento inicial máximo
   
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 3  # Knuth sugiere dividir por 3 cada vez
    return arr

# Probar la versión de la secuencia de Knuth
test_array = [33, 12, 56, 78, 2, 45, 67, 89, 1, 23]
print("Antes de ordenar con la secuencia de Knuth:", test_array)
print("Después de ordenar con la secuencia de Knuth:", shell_sort_knuth(test_array.copy()))

Características del algoritmo y análisis de complejidad

Complejidad temporal

El análisis de la complejidad temporal del ordenamiento Shell es muy complejo, ya que depende de la secuencia de incrementos elegida.

  • Peor caso: Al usar la secuencia original de Shell, la complejidad temporal en el peor caso es $O(n^2)$.
  • Caso promedio: Para buenas secuencias de incremento (como Knuth, Sedgewick), la complejidad temporal promedio está entre $O(n^{1.25})$ y $O(n^{1.5})$.
  • Mejor caso: Cuando el array ya está ordenado, la complejidad puede acercarse a $O(n \log n)$.

Complejidad espacial

  • El ordenamiento Shell esun algoritmo de ordenamiento in situque solo requiere espacio adicional de nivel constante (comotemp, gap, i, jvariables), por lo que la complejidad espacial es $O(1)$.

Estabilidad

  • El ordenamiento Shell esun algoritmo de ordenamiento inestable. Porque al ordenar por grupos según el incremento, los elementos iguales pueden ser asignados a diferentes subsecuencias y cambiar su orden relativo debido a los movimientos.

Comparación breve con otros algoritmos de ordenamiento

Característica Ordenamiento Shell Ordenamiento por inserción Ordenamiento por mezcla (Merge sort) Ordenamiento rápido (Quicksort)
Complejidad temporal promedio $O(n^{1.25})$ ~ $O(n^{1.5})$ $O(n^2)$ $O(n \log n)$ $O(n \log n)$
Complejidad espacial $O(1)$ $O(1)$ $O(n)$ $O(\log n)$
Estabilidad Inestable Estable Estable Inestable
Ventajas Buen rendimiento con volúmenes de datos medianos, ordenamiento in situ Simple, eficiente con datos pequeños o casi ordenados Estable, excelente complejidad temporal Más rápido en el caso promedio
Desventajas Análisis de complejidad difícil, la elección de la secuencia de incrementos tiene gran influencia Baja eficiencia con grandes volúmenes de datos Requiere espacio adicional El peor caso degenera a $O(n^2)$

Más ejemplos de código

Otras extensiones