Neste artigo, discutiremos o algoritmo de classificação de shell. Shell sort é a generalização da ordenação por inserção, que supera as desvantagens da ordenação por inserção comparando elementos separados por um intervalo de várias posições.
É um algoritmo de classificação que é uma versão estendida da classificação por inserção. A classificação Shell melhorou a complexidade média do tempo da classificação por inserção. Assim como a classificação por inserção, é um algoritmo de classificação baseado em comparação e no local. A classificação Shell é eficiente para conjuntos de dados de tamanho médio.
Na classificação por inserção, os elementos podem ser movidos apenas uma posição por vez. Para mover um elemento para uma posição distante, são necessários vários movimentos que aumentam o tempo de execução do algoritmo. Mas a classificação por shell supera essa desvantagem da classificação por inserção. Também permite a movimentação e troca de elementos distantes.
Este algoritmo primeiro classifica os elementos que estão distantes uns dos outros e, posteriormente, reduz a lacuna entre eles. Essa lacuna é chamada de intervalo. Este intervalo pode ser calculado usando o Knuth fórmula fornecida abaixo -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Agora, vamos ver o algoritmo de classificação de shell.
Algoritmo
As etapas simples para obter a classificação do shell estão listadas a seguir -
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;>
Funcionamento do algoritmo de classificação Shell
Agora, vamos ver o funcionamento do algoritmo de classificação de shell.
java int em string
Para entender o funcionamento do algoritmo de classificação de shell, vamos pegar um array não classificado. Será mais fácil entender a classificação do shell por meio de um exemplo.
Deixe os elementos do array serem -
Usaremos a sequência original de classificação de shell, ou seja, N/2, N/4,....,1 como intervalos.
No primeiro loop, n é igual a 8 (tamanho do array), então os elementos estão no intervalo de 4 (n/2 = 4). Os elementos serão comparados e trocados se não estiverem em ordem.
Aqui, no primeiro loop, o elemento no 0ºposição será comparada com o elemento em 4ºposição. Se o 0ºelemento for maior, ele será trocado pelo elemento em 4ºposição. Caso contrário, permanece o mesmo. Este processo continuará para os elementos restantes.
No intervalo de 4, as sublistas são {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Agora, temos que comparar os valores em cada sublista. Após a comparação, temos que trocá-los, se necessário, no array original. Depois de comparar e trocar, o array atualizado terá a seguinte aparência -
No segundo loop, os elementos estão no intervalo de 2 (n/4 = 2), onde n = 8.
Agora estamos tomando o intervalo de 2 para classificar o resto da matriz. Com intervalo de 2, serão geradas duas sublistas - {12, 25, 33, 40} e {17, 8, 31, 42}.
Agora, novamente temos que comparar os valores em cada sublista. Após a comparação, temos que trocá-los, se necessário, no array original. Depois de comparar e trocar, o array atualizado terá a seguinte aparência -
números abc
No terceiro loop, os elementos estão no intervalo de 1 (n/8 = 1), onde n = 8. Por fim, usamos o intervalo de valor 1 para classificar o restante dos elementos do array. Nesta etapa, a classificação shell usa classificação por inserção para classificar os elementos da matriz.
Agora, a matriz está classificada em ordem crescente.
Complexidade de classificação de shell
Agora, vamos ver a complexidade de tempo da classificação Shell no melhor caso, no caso médio e no pior caso. Veremos também a complexidade espacial da classificação Shell.
1. Complexidade de tempo
| Caso | Complexidade de tempo |
|---|---|
| Melhor caso | O(n*logn) |
| Caso médio | O(n*log(n)2) |
| Pior caso | Sobre2) |
2. Complexidade Espacial
| Complexidade Espacial | O(1) |
| Estábulo | NÃO |
- A complexidade do espaço da classificação Shell é O(1).
Implementação de classificação Shell
Agora, vamos ver os programas do Shell classificados em diferentes linguagens de programação.
Programa: Escreva um programa para implementar a classificação Shell em linguagem 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;>