"""
https://en.wikipedia.org/wiki/Shellsort#Pseudocode
"""


def shell_sort(collection: list[int]) -> list[int]:
    """Pure implementation of shell sort algorithm in Python
    :param collection:  Some mutable ordered collection with heterogeneous
    comparable items inside
    :return:  the same collection ordered by ascending

    >>> shell_sort([0, 5, 3, 2, 2])
    [0, 2, 2, 3, 5]
    >>> shell_sort([])
    []
    >>> shell_sort([-2, -5, -45])
    [-45, -5, -2]
    """
    # Marcin Ciura's gap sequence

    gaps = [701, 301, 132, 57, 23, 10, 4, 1]
    for gap in gaps:
        for i in range(gap, len(collection)):
            insert_value = collection[i]
            j = i
            while j >= gap and collection[j - gap] > insert_value:
                collection[j] = collection[j - gap]
                j -= gap
            if j != i:
                collection[j] = insert_value
    return collection


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    print(shell_sort(unsorted))

Declaración de problema

Dada una matriz no ordenada de n elementos, escriba una función para ordenar la matriz.

Enfoque

• Empezar con la brecha inicial, g
• Ir a través de los primeros (n - g) elementos en la matriz
• Comparar el elemento con el siguiente elemento que está a una distancia g
• Intercambiar los dos elementos si el primer elemento es más grande
• Disminuir la brecha y repetir hasta la brecha = 1

Complejidad temporal

La complejidad temporal depende de las secuencias de separación. Las complejidades de tiempo inferior se basan en las secuencias de separación de n/2^k.

O(n^2) Peor rendimiento en el caso

O(n) Mejor actuación en el caso

O(n^2) Rendimiento medio

Complejidad espacial

O(1) El peor caso

Nombre del Fundador

Donald Shell

Ejemplo

arr[] = {61, 109, 149, 111, 34, 2, 24, 119}
Brecha inicial: 4   

1. Índice = 0, Siguiente índice de elementos = 4
2. 61 > 34, swap 61 y 34
3. La matriz es ahora {34, 109, 149, 111, 61, 2, 24, 119}

4. Índice = 1, Siguiente índice de elementos = 5
5. 109 > 2, swap 109 y 2
6. La matriz es ahora {34, 2, 149, 111, 61, 109, 24, 119}

7. Índice = 2, Siguiente índice de elementos = 6
8. 149 > 24, swap 149 y 24
9. La matriz es ahora {34, 2, 24, 111, 61, 109, 149, 119}

10. Índice = 3, Siguiente índice de elementos = 7
11. 111 < 119, no hagan nada y continúen

12. Divida la brecha por 2 y repita hasta la brecha = 1

Explicación de vídeo

Un vídeo explicando el algoritmo del ordenamiento de Shell

Otros

La ordenación del shell también se conoce como clasificación de incremento de disminución.