Clasificación de Shell en Java

Shell Sort es un algoritmo de clasificación avanzado. Se considera que es una generalización de la ordenación por inserción y funciona comparando elementos muy separados. En este artículo, nos sumergiremos en la teoría y la implementación de Shell Sort.

Introducción

Los algoritmos de clasificación son algoritmos que reorganizan los miembros de una colección en un orden determinado. Los criterios de pedido pueden variar y, por lo general, los define el usuario.

En la práctica, el criterio de orden se proporciona al algoritmo como un método que compara dos objetos y devuelve:

  • 0: Si las entidades comparadas se consideran iguales
  • 1: si la primera entidad se considera mayor que la segunda
  • -1: si la segunda entidad se considera mayor que la primera

Dicho esto, esto se hace de manera más efectiva cuando la colección que estamos clasificando contiene objetos comparables, objetos que implementan la interfaz Comparable.

Este artículo trata sobre uno de los algoritmos más avanzados en particular: Shell Sort. Pero si desea leer más sobre algunos de los algoritmos de clasificación más comunes, consulte nuestro artículo Algoritmos de clasificación en Java, que aborda brevemente cada uno.

Clasificación de conchas {#clasificación de conchas}

La mayoría de los algoritmos de clasificación comparan elementos, en nuestro caso números, que están cerca entre sí de alguna manera. Un ejemplo sería Bubble Sort, que compara elementos adyacentes y los intercambia si es necesario. Shell Sort utiliza un enfoque completamente diferente, comparando elementos que están más separados al principio. Sin embargo, cuanto más clasificamos, más cerca se vuelven.

El espacio entre los elementos que estamos comparando (conocido como brecha) al principio se puede dar como uno de los argumentos al llamar al algoritmo. Shell Sort se considera una generalización de Insertion Sort, por lo que es útil trazar rápidamente un paralelo entre los dos y recapitular Insertion Sort por si acaso.

Parallels con clasificación por inserción

La ordenación por inserción coloca los elementos de una colección en su lugar ordenado uno a la vez seleccionando un elemento y comparándolo con cada elemento con un índice más bajo. Una vez que encuentra el lugar correcto para el elemento actual, se coloca y el proceso se repite.

Aquí hay un fragmento de código que debería ilustrar cómo funciona la ordenación por inserción. Toda la colección se desplaza hacia la derecha en el lugar correcto para "liberar" espacio para insertar un elemento.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public static void insertionSort(ArrayList<Integer> arr,int n) {
    int i, j, newValue;

    for (i = 1; i < n; i++) {
        newValue = arr.get(i);
        j = i;

        while (j > 0 && arr.get(j-1) > newValue) {
            arr.set(j,arr.get(j-1));
            j--;
        }
        arr.set(j,newValue);
    }
}

Shell Sort adopta el enfoque de inserción, pero en lugar de asignarle su posición exacta, en cada iteración acerca los elementos a su lugar. Cada pase se verá un poco más ordenado, hasta que finalmente lo esté.

Para entender cómo funciona esto, primero debemos explicar qué es una matriz ordenada por K y cuáles son sus características.

Matriz ordenada K

Supongamos que ‘A’ es una matriz de tamaño N. La matriz ‘A’ está ordenada según K si cada elemento está, como máximo, a K lugares de distancia de su posición de destino. En otras palabras, para cada i entre 1 y N, el lugar de destino de A[i] está en algún lugar entre i-K y 1+K en A.

Para una matriz de tamaño N sin ordenar, es posible ordenarla con K en tiempo O(N logK).

Una propiedad importante de las matrices ordenadas por K es que si la matriz ordenada por K~1~ está ordenada por K~2~, permanece ordenada por K~1~. Esto se puede probar fácilmente.

Caso Uno

$$
K_{1} > K_{2}
$$

Si A está clasificado K~1~, entonces cada elemento de A está como máximo K~1~ lugares alejado de su posición de destino. Si luego clasificamos A con K~2~, entonces cada elemento de A está como máximo a K~2~ lugares de distancia de su posición de destino. Dado que K~2~ es más pequeño que K~1~, si los elementos de A están a lo sumo K~2~ lugares de distancia de su objetivo, entonces deben estar más cerca de K~1~ lugares de su objetivo. Eso significa que si A está clasificado por K~2~, debe estar clasificado por K~1~.

Caso dos {#caso dos}

$$
K_{1} < K_{2}
$$

Cuando A está clasificado por K~1~, si lo clasificamos por K~2~, ningún elemento cambiará de lugar, porque A ya está clasificado por K~2~ (explicado en el caso anterior). Eso significa que también permanecerá ordenado por K~1~.

Ejemplo de clasificación de shell

A diferencia de Insertion Sort, donde cada vez que hacemos un intercambio, la colección se desplaza hacia la derecha, en Shell Sort los elementos cuyas posiciones cambiamos se agrupan y luego se ordenan dentro de los grupos. Después de ordenar los grupos, solo entonces se desplazan, lo que da como resultado que los elementos reales se muevan mucho menos.

A = [7, 13, 18, 22, 8, 29, 14, 7, 27, 25, 3]

Aquí, el número de elementos es 11.

Ahora, se supone que debemos elegir una brecha, entre los elementos que queremos comparar y luego agrupar:

$$
brecha = [\frac{11}{2}] = 5.
$$

A: 7, 13, 18, 22, 8, 29, 14, 7, 27, 25, 3

Ahora, hacemos grupos de números que están separados por 5 elementos (tienen 4 elementos entre ellos). Los grupos son (7, 29, 3), (13, 14), (18, 7), (22, 27), (8, 25).

Dado que N/2 se usa para el valor inicial de brecha, el primer grupo tiene 3 elementos y los demás tienen dos elementos cada uno debido a que nuestra colección tiene un número impar de elementos.

A: 7, 13, 18, 22, 8, 29, 14, 7, 27, 25, 3

No hay elementos en el primer grupo con un índice más pequeño que 0, por lo que comenzamos desde el segundo índice, cuyo valor es 29. El siguiente paso es comparar 29 con todos los elementos del grupo con índices más pequeños.

  • 7 < 29 es cierto, por lo que no se intercambiarán sus lugares.

No hay otros elementos en el grupo con un índice inferior a 5, por lo que terminamos con A[5].

El siguiente número del grupo es el 3, cuyo índice original es 10:

  • 29 < 3 es falso, por lo que se intercambiarán:

A: 7, 13, 18, 22, 8, 3, 14, 7, 27, 25, 29

Ahora, el valor de A[5] es 3. 29 debe estar en su lugar ordenado en el grupo, porque no hay ningún elemento con mayor índice en ese grupo. 3, por otro lado, aún podría ser más pequeño que los miembros del grupo con índices más bajos.

  • 7 < 3 es falso, por lo que se intercambiarán:

A: 3, 13, 18, 22, 8, 7, 14, 7, 27, 25, 29

No hay elementos en A con un índice inferior a 10 que no hayamos comparado con A[10]. Todos los miembros del primer grupo ahora están ordenados.

El siguiente grupo es (13, 14):

A: 3, 13, 18, 22, 8, 7, 14, 7, 27, 25, 29

Es fácil notar que si solo hay dos elementos en el grupo, se intercambian solo si el primero es más grande que el segundo. Los grupos que quedan ahora son (18, 7), (22, 27) y (8, 25) y el único grupo que necesitará intercambio será (18, 7):

A: 3, 13, 7, 22, 8, 7, 14, 18, 27, 25, 29

En este punto, no quedan grupos para analizar, por lo que la matriz está 5-ordenada. Aunque se ve mejor que antes, todavía no está del todo terminado.

Ahora, la brecha se divide por dos una vez más:

$$
brecha = [\frac{5}{2}] = 2
$$

Ahora, hacemos grupos de elementos que están separados por solo 2 elementos, lo que significa que solo hay un elemento entre ellos. Estos grupos son (3, 7, 8, 14, 27, 29) y (13, 22, 7, 18, 25):

A: 3, 13, 7, 22, 8, 7, 14, 18, 27, 25, *29 *

La clasificación cuando gap es 2 se mostrará en la clasificación 2 del segundo grupo.

A: 3, 13, 7, 22, 8, 7, 14, 18, 27, 25, 29

Estos dos grupos se ordenan de la misma manera que se ordenaron los grupos anteriores, y nos queda:

A: 3, 7, 7, 13, 8, 18, 14, 22, 27, 25, 29

Lo último que queda por hacer es ordenar 1 la matriz, que es, en realidad, ordenación por inserción.

Cada miembro se compara con todos los demás elementos con índices más pequeños. Lo importante a tener en cuenta aquí es que la matriz ya está ordenada en 2, por lo que solo es posible que los elementos en los lugares i e i+1 no estén ordenados. Por lo tanto, cuando se clasifica en 1, solo se pueden intercambiar los elementos que están uno al lado del otro.

Implementación

Con todo lo anterior en mente, implementemos Shell Sort. La invariante del bucle en el bucle for principal es que la matriz está ordenada por intervalos. El brecha se reduce a la mitad en cada iteración hasta que llega a 0. Cuando lo hace, la matriz se ordena:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public static void shSort(ArrayList<Integer> arr,int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i+= 1) {

            int temp = arr.get(i);
            int j;
            for (j = i; j >= gap && arr.get(j-gap) > temp; j -= gap)
                arr.set(j,arr.get(j-gap));
            arr.set(j,temp);
        }
    }
}

La matriz y su tamaño se dan como argumentos del método y el ciclo se ejecuta log~n~ veces.

El primer bucle for anidado pasa por grupos de elementos que están separados por brechas. Ese bucle se ejecuta n-gap veces. La variable temp es necesaria para el intercambio, como de costumbre.

Una de las condiciones en el segundo bucle for anidado es que j > gap, porque estamos comparando un elemento con todos los miembros del grupo con índices más pequeños de derecha a izquierda.

Debido a esto, el último número que se observará será el primer miembro del grupo. La segunda condición es que j-gap < temp. Esto significa que el ciclo se está ejecutando mientras hay elementos con índices más bajos que son más grandes que arr[j].

El primero que es más bajo rompe el bucle. Luego, arr[j] se mueve al índice cuyo valor era menor que. Este ciclo repite i/gap veces.

Complejidad del tiempo {#complejidad del tiempo}

Calculemos ahora la complejidad temporal de Shell Sort. Como ya se mencionó, el primer bucle se ejecuta log~n~ veces.

El segundo bucle comienza con brecha como índice, que es 2^k^. Dado que en el tercer bucle restamos brecha, eso significa que en la suma, i debe dividirse por brecha:

{estilo=“desbordamiento-x:desplazamiento”} $$\sum\limits_{k = 0}^{\log_{2}n}{\sum\limits_{i = 2^{k - 1}}^{n - 1}{\sum\limits_{j = 0}^{\frac{i}{2^{k - 1}}}{O(1)}}} = \sum\limits_{k = 0}^{\log_{2}n}{\sum\ límites_{i = 2^{k - 1}}^{n - 1}\frac{i}{2^{k - 1}}} = \sum\limits_{k = 0}^{\log_{2} n}\frac{1}{2^{k - 1}}{\sum\limits_{i = 2^{k - 1}}^{n - 1}i} = \sum\limits_{k = 0} ^{\log_{2}n}\frac{1}{2^{k - 1}} \ast \frac{(n - 1 - 2^{k - 1}) \ast (n - 2^{k - 1})}{2} = \sum\limits_{k = 0}^{\log_{2}n}\frac{(n - 1 - 2^{k - 1}) \ast (n - 2^ {k - 1})}{\frac{1}{2^{k}}} = \sum\limits_{k = 0}^{\log_{2}n}\frac{n^{2} - n - 2 \ast n2^{k - 1} + 2^{k - 1} + 2^{2k - 2}}{\frac{1}{2^{k}}} = \sum\limits_{k = 0}^{\log_{2}n}{\frac{n^{2}}{2^{k}} - \frac{n}{2^{k}} - n + \frac{1}{ 2} + 2^{k - 2}} = n^{2}\sum\limits_{k = 0}^{\log_{2}n}\frac{1}{2^{k}} - n\ suma\limits_{k = 0}^{\log_{2}n}\frac{1}{2^{k}} + (\frac{1}{2} - n)\log_{2}n + \ suma\limits_{k = 0}^{\log_{2}n}2^{k - 2} = n^{2}\frac{(\frac{1}{2})^{\log_{2} {n + 1}} - 1}{\frac{1}{2} - 1} - n\frac{(\frac{1}{2})^{\log_{2}{n + 1}}}{\frac{1}{2} - 1} + \frac{1}{4} \ast \frac{2^{\log_{2}{n + 1}} - 1}{2 - 1} + o(n\log n) = (2n^{2} - n)(1 - \frac{1}{2n}) + \frac{1}{4}(2n - 1) + o( n\log n) = 2n^{2} - \frac{3n}{2} + \frac{1}{4} + o(n\log n) = O(n^{2})$$

[*Desplácese para ver*]{.pequeño}

Todo esto lleva la complejidad del tiempo a O(n logn). Aquí, asumimos el hecho de que brecha se establece en n/2.

Si la brecha se establece de manera diferente, la complejidad del tiempo es diferente. Aquí, puedes leer más detalles sobre la complejidad temporal de Shell Sort dependiendo de la elección de la variable gap.

Conclusión

Shell Sort compara elementos que están más separados al principio, sin embargo, cuanto más los ordenamos, más cerca se vuelven, lo que da como resultado una matriz que está un poco más ordenada después de cada iteración.

Shell Sort funciona mejor que Insertion Sort, pero tiene una tasa de pérdida de caché mayor que Quick Sort.

If you want to read more about most common sorting algorithms, check out our article on Algoritmos de clasificación en Java.