Tässä artikkelissa käsittelemme shell-lajittelualgoritmia. Shell-lajittelu on lisäyslajittelun yleistys, joka poistaa lisäyslajittelun haitat vertaamalla elementtejä, jotka on erotettu useiden paikkojen väliltä.

Se on lajittelualgoritmi, joka on lisäyslajittelun laajennettu versio. Shell-lajittelu on parantanut lisäyslajittelun keskimääräistä aikamonimutkaisuutta. Kuten lisäyslajittelu, se on vertailupohjainen ja paikallaan oleva lajittelualgoritmi. Shell-lajittelu on tehokas keskikokoisille tietojoukoille.

Lisäyslajittelussa elementtejä voidaan siirtää kerrallaan vain yhden kohdan verran eteenpäin. Elementin siirtäminen kaukaiseen paikkaan vaatii monia liikkeitä, jotka lisäävät algoritmin suoritusaikaa. Mutta kuorilajittelu voittaa tämän lisäyslajittelun haitan. Se mahdollistaa myös kaukana olevien elementtien siirtämisen ja vaihtamisen.

Tämä algoritmi lajittelee ensin kaukana toisistaan ​​olevat elementit, minkä jälkeen se pienentää niiden välistä kuilua. Tätä aukkoa kutsutaan nimellä intervalli. Tämä intervalli voidaan laskea käyttämällä Knuthin alla oleva kaava -

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

Katsotaan nyt shell-lajittelun algoritmia.

Algoritmi

Yksinkertaiset vaiheet kuorilajittelun saavuttamiseksi on lueteltu seuraavasti -

java int merkkijonoon

 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;>

Shell-lajittelualgoritmin toiminta

Katsotaan nyt komentotulkkilajittelualgoritmin toimintaa.

Ymmärtääksesi shell-lajittelualgoritmin toiminnan, otetaan lajittelematon matriisi. Shell-lajittelu on helpompi ymmärtää esimerkin avulla.

Olkoon taulukon elementit -

Käytämme aikaväleinä alkuperäistä shell-lajittelusekvenssiä, eli N/2, N/4,....,1.

Ensimmäisessä silmukassa n on yhtä kuin 8 (taulukon koko), joten elementit ovat välissä 4 (n/2 = 4). Elementtejä verrataan ja vaihdetaan, jos ne eivät ole järjestyksessä.

Tässä, ensimmäisessä silmukassa, elementti kohdassa 0^thsijaintia verrataan elementtiin kohdassa 4^thasema. Jos 0^thelementti on suurempi, se vaihdetaan elementin kanssa 4^thasema. Muuten se pysyy samana. Tätä prosessia jatketaan muiden elementtien osalta.

Välillä 4 alaluettelot ovat {33, 12}, {31, 17}, {40, 25}, {8, 42}.

Nyt meidän on verrattava arvoja jokaisessa aliluettelossa. Vertailun jälkeen meidän on vaihdettava ne tarvittaessa alkuperäisessä taulukossa. Vertailun ja vaihdon jälkeen päivitetty matriisi näyttää tältä -

Toisessa silmukassa elementit ovat välillä 2 (n/4 = 2), missä n = 8.

Nyt otamme välin 2 lajitellaksesi loput taulukosta. Välillä 2 luodaan kaksi alaluetteloa - {12, 25, 33, 40} ja {17, 8, 31, 42}.

merkkijono kokonaisluvuksi

Nyt meidän on jälleen verrattava arvoja jokaisessa aliluettelossa. Vertailun jälkeen meidän on vaihdettava ne tarvittaessa alkuperäisessä taulukossa. Vertailun ja vaihdon jälkeen päivitetty matriisi näyttää tältä -

Kolmannessa silmukassa elementit ovat välissä 1 (n/8 = 1), missä n = 8. Lopuksi käytämme arvon 1 väliä lajittelemaan loput taulukon elementit. Tässä vaiheessa komentotulkkilajittelu käyttää lisäyslajittelua taulukon elementtien lajitteluun.

Nyt matriisi on lajiteltu nousevaan järjestykseen.

Shell lajittelun monimutkaisuus

Katsotaan nyt Shell-lajittelun aikamonimutkaisuus parhaassa tapauksessa, keskimääräisessä tapauksessa ja pahimmassa tapauksessa. Näemme myös Shell-lajin avaruuden monimutkaisuuden.

1. Aika monimutkaisuus

Paras tapauksen monimutkaisuus -Se tapahtuu, kun lajittelua ei vaadita, eli matriisi on jo lajiteltu. Shell-lajittelun paras aika monimutkaisuus on O(n*logn). Keskimääräinen tapauksen monimutkaisuus -Se tapahtuu, kun taulukon elementit ovat sekaisin järjestyksessä, joka ei ole oikein nouseva eikä oikein laskeva. Shell-lajittelun tapauksen keskimääräinen aika monimutkaisuus on O(n*logn). Pahimman tapauksen monimutkaisuus -Se tapahtuu, kun taulukon elementit on lajiteltava käänteisessä järjestyksessä. Tämä tarkoittaa, että sinun on lajiteltava taulukon elementit nousevaan järjestykseen, mutta sen elementit ovat laskevassa järjestyksessä. Shell-lajittelun pahin aika monimutkaisuus on Päällä²).

2. Tilan monimutkaisuus

• Shell-lajittelun avaruuden monimutkaisuus on O(1).

Shell-lajin käyttöönotto

Katsotaanpa nyt Shellin ohjelmien lajittelua eri ohjelmointikielillä.

Ohjelmoida: Kirjoita ohjelma Shell-lajittelun toteuttamiseksi C-kielellä.

 #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;>