logo

Algoritmus triedenia škrupín

V tomto článku budeme diskutovať o algoritme triedenia shellu. Shell sort je zovšeobecnenie typu vkladania, ktoré prekonáva nevýhody triedenia vkladaním porovnaním prvkov oddelených medzerou niekoľkých pozícií.

nastavenia internetového prehliadača

Je to triediaci algoritmus, ktorý je rozšírenou verziou triedenia vkladania. Shell sort zlepšil priemernú časovú zložitosť triedenia vkladania. Podobne ako pri triedení vkladania ide o algoritmus triedenia na mieste založenom na porovnaní. Shell sort je efektívny pre stredne veľké súbory údajov.

Pri triedení vkladania je možné prvky posúvať dopredu len o jednu pozíciu. Na presunutie prvku do vzdialenej polohy je potrebných veľa pohybov, ktoré predĺžia čas vykonania algoritmu. Ale triedenie shell prekonáva túto nevýhodu triedenia vkladania. Umožňuje pohyb a výmenu aj vzdialených prvkov.

Tento algoritmus najskôr triedi prvky, ktoré sú od seba vzdialené, a následne zmenšuje medzeru medzi nimi. Táto medzera sa nazýva ako interval. Tento interval možno vypočítať pomocou Knuthova vzorec uvedený nižšie -

 h = h * 3 + 1 where, 'h' is the interval having initial value 1. 

Teraz sa pozrime na algoritmus triedenia shellu.

Algoritmus

Jednoduché kroky na dosiahnutie triedenia shellu sú uvedené nasledovne -

 ShellSort(a, n) // &apos;a&apos; is the given array, &apos;n&apos; is the size of array for (interval = n/2; interval &gt; 0; interval /= 2) for ( i = interval; i <n; i +="1)" temp="a[i];" for (j="i;" j>= interval &amp;&amp; a[j - interval] &gt; temp; j -= interval) a[j] = a[j - interval]; a[j] = temp; End ShellSort </n;>

Fungovanie algoritmu triedenia Shell

Teraz sa pozrime na fungovanie algoritmu triedenia shellu.

Aby sme pochopili fungovanie algoritmu triedenia shellu, zoberme si netriedené pole. Pomocou príkladu bude jednoduchšie pochopiť triedenie shellu.

Nech sú prvky poľa -

Algoritmus triedenia škrupín

Ako intervaly použijeme pôvodnú postupnosť triedenia shell, t.j. N/2, N/4,....,1.

V prvej slučke sa n rovná 8 (veľkosť poľa), takže prvky ležia v intervale 4 (n/2 = 4). Prvky sa porovnajú a vymenia, ak nie sú v poriadku.

rímske číslice 1 100

Tu, v prvej slučke, prvok na 0thpozícia sa porovná s prvkom na 4thpozíciu. Ak je 0thprvok je väčší, bude zamenený s prvkom na 4thpozíciu. V opačnom prípade to zostáva rovnaké. Tento proces bude pokračovať pre zostávajúce prvky.

V intervale 4 sú podzoznamy {33, 12}, {31, 17}, {40, 25}, {8, 42}.

Algoritmus triedenia škrupín

Teraz musíme porovnať hodnoty v každom podzozname. Po porovnaní ich musíme v prípade potreby vymeniť v pôvodnom poli. Po porovnaní a výmene bude aktualizované pole vyzerať takto -

Algoritmus triedenia škrupín

V druhej slučke prvky ležia v intervale 2 (n/4 = 2), kde n = 8.

Teraz berieme interval 2 na triedenie zvyšku poľa. V intervale 2 sa vygenerujú dva podzoznamy – {12, 25, 33, 40} a {17, 8, 31, 42}.

previesť reťazec na celé číslo
Algoritmus triedenia škrupín

Teraz musíme opäť porovnať hodnoty v každom podzozname. Po porovnaní ich musíme v prípade potreby vymeniť v pôvodnom poli. Po porovnaní a výmene bude aktualizované pole vyzerať takto -

Algoritmus triedenia škrupín

V tretej slučke prvky ležia v intervale 1 (n/8 = 1), kde n = 8. Nakoniec použijeme interval s hodnotou 1 na triedenie zvyšku prvkov poľa. V tomto kroku triedenie shell používa triedenie vložením na triedenie prvkov poľa.

Algoritmus triedenia škrupín

Teraz je pole zoradené vo vzostupnom poradí.

Zložitosť triedenia škrupín

Teraz sa pozrime na časovú zložitosť triedenia Shell v najlepšom prípade, priemernom prípade a najhoršom prípade. Uvidíme aj priestorovú náročnosť druhu Shell.

1. Časová zložitosť

Prípad Časová zložitosť
Najlepší prípad O(n*logn)
Priemerný prípad O(n*log(n)2)
V najhoršom prípade O(n2)
    Najlepšia zložitosť prípadu -Vyskytuje sa, keď nie je potrebné žiadne triedenie, t. j. pole je už zoradené. Najlepšia časová zložitosť zoradenia Shell je O(n*logn). Priemerná zložitosť prípadu -Vyskytuje sa vtedy, keď sú prvky poľa v premiešanom poradí, ktoré nie je správne vzostupné a nesprávne zostupné. Priemerná časová zložitosť prípadu zoradenia Shell je O(n*logn). Zložitosť najhoršieho prípadu -Vyskytuje sa, keď sa vyžaduje, aby boli prvky poľa zoradené v opačnom poradí. To znamená, že musíte zoradiť prvky poľa vo vzostupnom poradí, ale jeho prvky sú v zostupnom poradí. Najhorší prípad časovej zložitosti druhu Shell je O(n2).

2. Zložitosť priestoru

Vesmírna zložitosť O(1)
Stabilný NIE
  • Priestorová zložitosť triedenia Shell je O(1).

Implementácia typu Shell

Teraz sa pozrime na triedenie programov Shell v rôznych programovacích jazykoch.

Program: Napíšte program na implementáciu triedenia Shell v jazyku 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 &gt; 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 &amp;&amp; a[j - interval] &gt; 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 &gt; 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 &amp;&amp; a[j - interval] &gt; 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 &gt; 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 &amp;&amp; a[j - interval] &gt; 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 &gt; 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 &amp;&amp; a[j - interval] &gt; 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&apos;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;>