En este artículo, analizaremos el algoritmo de clasificación de shell. La clasificación Shell es la generalización de la clasificación por inserción, que supera los inconvenientes de la clasificación por inserción al comparar elementos separados por un espacio de varias posiciones.
Es un algoritmo de clasificación que es una versión extendida de la clasificación por inserción. La clasificación de Shell ha mejorado la complejidad del tiempo promedio de la clasificación por inserción. Al igual que la ordenación por inserción, es un algoritmo de ordenación in situ basado en comparaciones. La clasificación de shell es eficaz para conjuntos de datos de tamaño mediano.
En la ordenación por inserción, los elementos a la vez pueden avanzar solo una posición. Para mover un elemento a una posición lejana se requieren muchos movimientos que aumentan el tiempo de ejecución del algoritmo. Pero la ordenación por shell supera este inconveniente de la ordenación por inserción. También permite el movimiento e intercambio de elementos lejanos.
Este algoritmo primero ordena los elementos que están lejos unos de otros y luego reduce la brecha entre ellos. Esta brecha se llama como intervalo. Este intervalo se puede calcular utilizando el knuth's fórmula dada a continuación -
si no java
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Ahora, veamos el algoritmo de clasificación de shell.
Algoritmo
Los pasos simples para lograr la clasificación de shell se enumeran a continuación:
ShellSort(a, n) // 'a' is the given array, 'n' is the size of array for (interval = n/2; interval > 0; interval /= 2) for ( i = interval; i <n; i +="1)" temp="a[i];" for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; a[j] = temp; End ShellSort </n;>
Funcionamiento del algoritmo de clasificación de Shell
Ahora, veamos el funcionamiento del algoritmo de clasificación de shell.
Para comprender el funcionamiento del algoritmo de ordenación del shell, tomemos una matriz sin clasificar. Será más fácil entender la clasificación de shell mediante un ejemplo.
Dejemos que los elementos de la matriz sean:
Usaremos la secuencia original de clasificación de shell, es decir, N/2, N/4,....,1 como intervalos.
En el primer ciclo, n es igual a 8 (tamaño de la matriz), por lo que los elementos se encuentran en el intervalo de 4 (n/2 = 4). Los elementos se compararán e intercambiarán si no están en orden.
Aquí, en el primer bucle, el elemento en el 0thLa posición se comparará con el elemento en 4.thposición. si el 0thelemento es mayor, se intercambiará con el elemento en 4thposición. Por lo demás, sigue igual. Este proceso continuará para los elementos restantes.
En el intervalo de 4, las sublistas son {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Ahora, tenemos que comparar los valores en cada sublista. Después de comparar, tenemos que intercambiarlos si es necesario en la matriz original. Después de comparar e intercambiar, la matriz actualizada tendrá el siguiente aspecto:
mapa de reacciones
En el segundo bucle, los elementos se encuentran en el intervalo de 2 (n/4 = 2), donde n = 8.
Ahora estamos tomando el intervalo de 2 para ordenar el resto de la matriz. Con un intervalo de 2, se generarán dos sublistas: {12, 25, 33, 40} y {17, 8, 31, 42}.
Ahora, nuevamente tenemos que comparar los valores en cada sublista. Después de comparar, tenemos que intercambiarlos si es necesario en la matriz original. Después de comparar e intercambiar, la matriz actualizada tendrá el siguiente aspecto:
En el tercer ciclo, los elementos se encuentran en el intervalo de 1 (n/8 = 1), donde n = 8. Por último, usamos el intervalo de valor 1 para ordenar el resto de los elementos de la matriz. En este paso, la ordenación de shell utiliza la ordenación por inserción para ordenar los elementos de la matriz.
Ahora, la matriz está ordenada en orden ascendente.
Complejidad de clasificación de shell
Ahora, veamos la complejidad temporal de la clasificación de Shell en el mejor de los casos, el caso promedio y el peor de los casos. También veremos la complejidad espacial del tipo Shell.
1. Complejidad del tiempo
| Caso | Complejidad del tiempo |
|---|---|
| Mejor caso | O(n*logn) |
| Caso promedio | O(n*log(n)2) |
| Peor de los casos | En2) |
2. Complejidad espacial
| Complejidad espacial | O(1) |
| Estable | NO |
- La complejidad espacial del tipo Shell es O (1).
Implementación de tipo Shell
Ahora, veamos los programas de Shell ordenados en diferentes lenguajes de programación.
Programa: Escriba un programa para implementar Shell sort en lenguaje C.
#include /* function to implement shellSort */ int shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval > 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; // put temp (the original a[i]) in its correct position a[j] = temp; } } return 0; } void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 42 i++) printf('%d ', a[i]); } int main() { a[]="{" 33, 31, 40, 8, 12, 17, 25, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are -
'); printarr(a, n); shell(a, printf('
after applying shell sort, the return 0; < pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-7.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in C++.</p> <pre> #include using namespace std; /* function to implement shellSort */ int shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval > 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; // put temp (the original a[i]) in its correct position a[j] = temp; } } return 0; } void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 41 i++) cout< <a[i]<<' '; } int main() { a[]="{" 32, 30, 39, 7, 11, 16, 24, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are -
'; printarr(a, n); shell(a, cout<<'
after applying shell sort, the return 0; < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-8.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in C#.</p> <pre> using System; class ShellSort { /* function to implement shellSort */ static void shell(int[] a, int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval > 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; /* put temp (the original a[i]) in its correct position */ a[j] = temp; } } } static void printArr(int[] a, int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 40 i++) console.write(a[i] + ' '); } static void main() { int[] a="{" 31, 29, 38, 6, 10, 15, 23, }; int n="a.Length;" console.write('before sorting array elements are -
'); printarr(a, n); shell(a, console.write('
after applying shell sort, the < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-9.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in Java.</p> <pre> class ShellSort { /* function to implement shellSort */ static void shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval > 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; /* put temp (the original a[i]) in its correct position */ a[j] = temp; } } } static void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 39 i++) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{" 30, 28, 37, 5, 9, 14, 22, }; n="a.length;" system.out.print('before sorting array elements are -
'); printarr(a, n); shell(a, system.out.print('
after applying shell sort, the < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-10.webp" alt="Shell Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></n;></pre></n;></n;></pre></n;></n;></pre></n;></n;>