Algoritmo de clasificación de shell con EJEMPLO

¿Qué es la clasificación de conchas?

El método de Shell, o ordenación de Shell en la estructura de datos, es un algoritmo eficiente de ordenación por comparación in situ. Lleva el nombre de Donald Shell cuando propuso la idea inicial en 1959. La ordenación de Shell es una extensión generalizada del algoritmo de ordenación por inserción.

La idea fundamental de este algoritmo de ordenación es agrupar los elementos que están muy separados y ordenarlos en consecuencia. Luego, disminuye gradualmente la brecha entre ellos. La ordenación de shell supera la complejidad de tiempo promedio del caso de la ordenación por inserción al comparar e intercambiar elementos que están muy alejados.

Esta brecha, conocida como intervalo, se reduce de acuerdo con algunas secuencias de brechas óptimas. El tiempo de ejecución de la clasificación de shell también depende de estas secuencias. Hay varias secuencias de espacios, como la secuencia original de Shell, la fórmula de Knuth, los incrementos de Hibbard, etc. La secuencia de espacios original de Shell es: n/2, n/4, n/8, ……….1

Algoritmo de clasificación de shell

Los pasos o procedimiento para el algoritmo de clasificación de shell son los siguientes:

Paso 1) Inicialice el valor del intervalo, h = n/2. (En este ejemplo, n es el tamaño de la matriz)

Paso 2) Coloque todos los elementos dentro de una distancia del intervalo h en una sublista.

Paso 3) Ordene esas sublistas mediante ordenación por inserción.

Paso 4) Establezca un nuevo intervalo, h=h/2.

Paso 5) Si h>0, vaya al paso 2. En caso contrario, vaya al paso 6.

Paso 6) La salida resultante será la matriz ordenada.

Cómo funciona la clasificación de shell

En la ordenación por inserción, los elementos se mueven solo una posición a la vez. Por el contrario, la ordenación de shell divide la matriz en partes más pequeñas según el valor del intervalo y ejecuta la ordenación por inserción en esas partes.

Gradualmente, el valor del intervalo disminuye y el tamaño de las piezas divididas aumenta. Como las piezas se clasifican individualmente de antemano, fusionarlas requiere menos pasos que el proceso. tipo de inserción.

El siguiente GIF muestra una demostración de la ordenación por shell. En esta demostración, el valor indicado en rojo y azul se compara y se intercambia en función de la ordenación por inserción. Luego, el intervalo disminuye y la ordenación por shell inicia la ordenación por inserción en esos datos casi ordenados.

Funcionamiento del algoritmo de clasificación de Shell

Veamos el siguiente ejemplo de un algoritmo de ordenación de shell. En este ejemplo, ordenaremos la siguiente matriz mediante ordenación de shell:

Paso 1) Aquí, el tamaño de la matriz es 8. Por lo tanto, el valor del intervalo será h = 8/2 o 4.

Paso 2) Ahora, almacenaremos todos los elementos a una distancia de 4. Para nuestro caso, las sublistas son: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Paso 3) Ahora, esas sublistas se ordenarán mediante ordenamiento por inserción, donde se utiliza una variable temporal para comparar ambos números y ordenar en consecuencia.

La matriz sería como la siguiente después de intercambiar operaciones:

Paso 4) Ahora, disminuiremos el valor inicial del intervalo. El nuevo intervalo será h=h/2 o 4/2 o 2.

Paso 5) Como 2>0, iremos al paso 2 para almacenar todos los elementos a una distancia de 2. Para este momento, las sublistas son:

{1, 5, 8, 7}, {4, 2, 6, 3}

Luego, estas sublistas se ordenarán mediante ordenamiento por inserción. Después de comparar e intercambiar la primera sublista, la matriz será la siguiente.

Después de ordenar la segunda sublista, la matriz original será:

Por otra parte, el intervalo se reducirá. Ahora el intervalo será h=h/2 o 2/1 o 1. Por lo tanto, usaremos el algoritmo de ordenación por inserción para ordenar la matriz modificada.

A continuación se muestra la descripción del procedimiento paso a paso de la ordenación por inserción.

El intervalo se divide nuevamente por 2. En ese momento, el intervalo se vuelve 0. Entonces vamos al paso 6.

Paso 6) Como el intervalo es 0, la matriz se ordena por este tiempo. La matriz ordenada es-

Pseudocódigo

Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
    for (i = interval; i & lt; n; i += 1)
        temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; temp; j -= interval)
    a[j] = a[j - interval];
a[j] = temp;
End

Programa de clasificación de Shell en C/C++

Entrada:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

Salida:

Sorted Output:

1 2 3 4 5 6 7 8

Ejemplo de ordenación de shell en Python

Entrada:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

Salida:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Aplicaciones de Shell Sort

Aquí hay aplicaciones importantes de Shell Sort:

• La clasificación de conchas se utiliza en el Kernel Linux porque no utiliza una pila de llamadas.
• La biblioteca uClibc utiliza la clasificación Shell.
• El compresor bzip2 utiliza Shell sort para evitar exceder la recursividad.

Ventajas y desventajas de la clasificación de conchas

Ventajas	Desventajas
No se requiere ninguna llamada a la pila.	No es eficiente para matrices de gran tamaño.
Fácil implementación.	Ineficiente para elementos muy dispersos.
Eficiente para elementos menos espaciados.

Análisis de complejidad de ordenamiento de shell

Complejidad temporal de la ordenación de shell

La complejidad temporal del algoritmo de ordenamiento de capas es O(n^2). El razonamiento es el siguiente:

En el mejor de los casos, la cantidad total de pruebas para todos los intervalos cuando la matriz estaba organizada previamente es igual a log n. Por lo tanto, la complejidad sería O(n*log n).

Para el peor de los casos, consideremos que la matriz consta de tal manera que los elementos requieren el mayor número de comparaciones. Entonces todos los elementos no se compararán ni cambiarán hasta la última iteración. Por lo tanto, las comparaciones totales necesarias para el incremento final son O (n^2).

En conclusión, las complejidades temporales serían

1. Mejor complejidad del caso: O(n*log n)
2. Complejidad media del caso: O(n*log n)
3. Complejidad del peor caso: O(n^2)

La complejidad del tiempo de ejecución de la ordenación por shell depende en gran medida de las secuencias de incremento de espacios que se utilicen. Sin embargo, todavía se desconoce cuál es la mejor secuencia de incremento para la ordenación por shell.

Complejidad del espacio de ordenamiento de capas

En esta clasificación por comparación, no necesitamos ningún espacio auxiliar adicional, por lo que la complejidad espacial de este tipo de algoritmo es O(1).