"SHELL SORT"

 

 

 Es una mejora del método de inserción directa que se utiliza cuando el número de elementos a ordenar es grande. El método se denomina “shell” –en honor de su inventor Donald shell – y también método de inserción con incrementos decrecientes.

En el método de clasificación por inserción, cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es más pequeño - por ejemplo -, hay que ejecutar muchas comparaciones antes de colocarlo en su lugar definitivamente. Shell modifico los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño y con eso se conseguía la clasificación más rápida. El método se basa en fijar el tamaño de los saltos constantes, pero de mas de una posición.

Supongamos un vector de elementos

4          12        16        24        36        3

 

En el método de inserción directa, los saltos se hacen de una posición en una posición y se necesitaran cinco comparaciones. En el método de Shell, si los saltos son de dos posiciones, se realizaran comparaciones.

            4          12        16        24        36        3

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

Considerando la variable salto, se tendría para el caso de un determinado vector X los siguientes recorridos:

Vector X         [X[1], X[3],  …,X[N]]

Vector X1       [X[1], X[1] + salto, X[2],  …]

Vector XN      [salto1, salto2, salto3,  …]

EJEMPLO :

Deducir las secuencias parciales de clasificación por el método de Shell para ordenar en ascendente la lista o vector.

6,   1,         5,         2,         3,         4,         0

 

 

RECORRIDO

SALTO

LISTA REORDENADA

INTERCAMBIO

1

3

2,1,4,5,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

 

 

Sea un vector X:

X[1], X[2], X[3],  …X[N]

Y consideremos el primer salto a dar que tendrá un valor de N/2

Por lo que, para reordenar, se tomara parte entera. N  DIV  2

Y iguala a salto  Salto = N  DIV  2

 

 

Private Sub Command1_Click()

    Dim l(1 To 20), salto As Integer

    n = InputBox("digite el número elementos de la lista", "control de entrada")

    For i = 1 To n

        l(i) = InputBox("digite el número", "control de entrada")

    Next i

    salto = n / 2

    While salto > 0

        For i = (salto + 1) To n

            j = i - salto

            While j > 0

                k = j + salto

                If l(j) <= l(k) Then

                    j = 0

                Else

                    aux = l(j)

                    l(j) = l(k)

                    l(k) = aux

                End If

                j = j - salto

            Wend

        Next i

        salto = salto / 2

    Wend

    For i = 1 To n

        Print l(i)

    Next i

End Sub