V tomto článku budeme diskutovat o algoritmu řazení shellu. Shell sort je zobecněním řazení vkládání, které překonává nevýhody řazení vkládáním porovnáním prvků oddělených mezerou několika pozic.
Je to třídicí algoritmus, který je rozšířenou verzí řazení vkládání. Shell sort zlepšil průměrnou časovou složitost řazení vložení. Podobně jako u řazení vložení se jedná o algoritmus řazení založený na porovnání a na místě. Shell sort je efektivní pro středně velké soubory dat.
Při řazení vkládání lze prvky najednou posunout dopředu pouze o jednu pozici. K přesunutí prvku do vzdálené polohy je zapotřebí mnoho pohybů, které prodlužují dobu provádění algoritmu. Ale shellové řazení překonává tuto nevýhodu vkládání. Umožňuje pohyb a výměnu i vzdálených prvků.
Tento algoritmus nejprve třídí prvky, které jsou od sebe daleko, a následně mezi nimi zmenšuje mezeru. Tato mezera se nazývá jako interval. Tento interval lze vypočítat pomocí Knuthova vzorec uvedený níže -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Nyní se podívejme na algoritmus řazení shellu.
Algoritmus
Jednoduché kroky k dosažení řazení shellu jsou uvedeny následovně -
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;>
Fungování algoritmu řazení Shell
Nyní se podívejme na fungování algoritmu řazení shellu.
Abychom pochopili fungování algoritmu řazení shellu, vezměme si netříděné pole. Pomocí příkladu bude snazší pochopit řazení shellu.
Nechť prvky pole jsou -
Jako intervaly použijeme původní sekvenci řazení shellu, tj. N/2, N/4,....,1.
V první smyčce je n rovno 8 (velikost pole), takže prvky leží v intervalu 4 (n/2 = 4). Prvky budou porovnány a vyměněny, pokud nebudou v pořádku.
Zde, v první smyčce, prvek na 0čtpozice bude porovnána s prvkem na 4čtpozice. Pokud je 0čtje prvek větší, bude zaměněn za prvek na 4čtpozice. Jinak to zůstává stejné. Tento proces bude pokračovat u zbývajících prvků.
V intervalu 4 jsou dílčí seznamy {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Nyní musíme porovnat hodnoty v každém dílčím seznamu. Po porovnání je musíme v případě potřeby zaměnit v původním poli. Po porovnání a výměně bude aktualizované pole vypadat následovně -
abeceda a čísla
Ve druhé smyčce leží prvky v intervalu 2 (n/4 = 2), kde n = 8.
Nyní bereme interval 2 seřadit zbytek pole. V intervalu 2 budou vygenerovány dva dílčí seznamy – {12, 25, 33, 40} a {17, 8, 31, 42}.
Nyní musíme opět porovnat hodnoty v každém dílčím seznamu. Po porovnání je musíme v případě potřeby zaměnit v původním poli. Po porovnání a výměně bude aktualizované pole vypadat následovně -
Ve třetí smyčce leží prvky v intervalu 1 (n/8 = 1), kde n = 8. Nakonec použijeme interval hodnoty 1 k seřazení zbytku prvků pole. V tomto kroku řazení shellu používá řazení vložením k řazení prvků pole.
Nyní je pole seřazeno ve vzestupném pořadí.
Složitost řazení shellů
Nyní se podívejme na časovou složitost řazení Shell v nejlepším případě, průměrném případě a nejhorším případě. Uvidíme také vesmírnou složitost druhu Shell.
1. Časová složitost
| Pouzdro | Časová složitost |
|---|---|
| Nejlepší případ | O(n*logn) |
| Průměrný případ | O(n*log(n)2) |
| Nejhorší případ | Na2) |
2. Prostorová složitost
| Vesmírná složitost | O(1) |
| Stabilní | NE |
- Prostorová složitost řazení Shell je O(1).
Implementace typu Shell
Nyní se podívejme na řazení programů Shell v různých programovacích jazycích.
Program: Napište program pro implementaci Shell sort v jazyce 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;>