Šajā rakstā mēs apspriedīsim čaulas kārtošanas algoritmu. Apvalka kārtošana ir ievietošanas kārtošanas vispārinājums, kas novērš ievietošanas kārtošanas trūkumus, salīdzinot elementus, kas atdalīti ar vairāku pozīciju atstarpi.
Tas ir šķirošanas algoritms, kas ir paplašināta ievietošanas kārtošanas versija. Apvalka kārtošana ir uzlabojusi ievietošanas kārtošanas vidējo sarežģītību laikā. Tāpat kā ievietošanas kārtošanai, tas ir uz salīdzināšanu balstīts un vietā veikts kārtošanas algoritms. Apvalka kārtošana ir efektīva vidēja lieluma datu kopām.
Ievietošanas kārtošanā elementus vienlaikus var pārvietot tikai par vienu pozīciju. Lai pārvietotu elementu uz tālu vietu, ir nepieciešamas daudzas kustības, kas palielina algoritma izpildes laiku. Bet čaulas šķirošana novērš šo ievietošanas kārtošanas trūkumu. Tas ļauj pārvietot un apmainīt arī tālu esošos elementus.
Šis algoritms vispirms sašķiro elementus, kas atrodas tālu viens no otra, un pēc tam samazina atstarpi starp tiem. Šo plaisu sauc par intervāls. Šo intervālu var aprēķināt, izmantojot Knuts formula dota zemāk -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Tagad apskatīsim čaulas kārtošanas algoritmu.
Algoritms
Vienkāršās darbības, lai sasniegtu čaulas kārtošanu, ir uzskaitītas šādi:
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;>
Shell šķirošanas algoritma darbība
Tagad apskatīsim čaulas kārtošanas algoritma darbību.
Lai saprastu čaulas kārtošanas algoritma darbību, ņemsim nešķirotu masīvu. Izmantojot piemēru, būs vieglāk saprast čaulas kārtošanu.
kas ir dubultā java
Lai masīva elementi ir -
Kā intervālus izmantosim sākotnējo čaulas kārtošanas secību, t.i., N/2, N/4,....,1.
Pirmajā cilpā n ir vienāds ar 8 (masīva lielums), tāpēc elementi atrodas intervālā 4 (n/2 = 4). Elementi tiks salīdzināti un apmainīti, ja tie nebūs kārtībā.
Šeit, pirmajā cilpā, elements pie 0thpozīcija tiks salīdzināta ar elementu 4thpozīciju. Ja 0thelements ir lielāks, tas tiks aizstāts ar elementu 4thpozīciju. Pretējā gadījumā tas paliek nemainīgs. Šis process turpināsies attiecībā uz pārējiem elementiem.
Ar intervālu 4 apakšsaraksti ir {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Tagad mums ir jāsalīdzina vērtības katrā apakšsarakstā. Pēc salīdzināšanas mums tie ir jāmaina, ja nepieciešams sākotnējā masīvā. Pēc salīdzināšanas un apmaiņas atjauninātais masīvs izskatīsies šādi -
Otrajā cilpā elementi atrodas intervālā 2 (n/4 = 2), kur n = 8.
Tagad mēs ņemam intervālu no 2 lai sakārtotu pārējo masīvu. Ar intervālu 2 tiks ģenerēti divi apakšsaraksti — {12, 25, 33, 40} un {17, 8, 31, 42}.
Tagad mums atkal ir jāsalīdzina vērtības katrā apakšsarakstā. Pēc salīdzināšanas mums tie ir jāmaina, ja nepieciešams sākotnējā masīvā. Pēc salīdzināšanas un apmaiņas atjauninātais masīvs izskatīsies šādi -
Trešajā cilpā elementi atrodas intervālā 1 (n/8 = 1), kur n = 8. Visbeidzot, mēs izmantojam vērtības 1 intervālu, lai sakārtotu pārējos masīva elementus. Šajā darbībā čaulas kārtošana izmanto ievietošanas kārtošanu, lai kārtotu masīva elementus.
izrakstīšanās gitā
Tagad masīvs ir sakārtots augošā secībā.
Apvalka šķirošanas sarežģītība
Tagad apskatīsim Shell kārtošanas laika sarežģītību labākajā, vidējā un sliktākajā gadījumā. Mēs redzēsim arī Shell šķirošanas kosmosa sarežģītību.
1. Laika sarežģītība
| Lieta | Laika sarežģītība |
|---|---|
| Labākais gadījums | O(n*logn) |
| Vidējais gadījums | O(n*log(n)2) |
| Sliktākajā gadījumā | O(n2) |
2. Telpas sarežģītība
| Kosmosa sarežģītība | O(1) |
| Stabils | NĒ |
- Shell šķirošanas telpas sarežģītība ir O(1).
Shell šķirošanas ieviešana
Tagad apskatīsim Shell programmu šķirošanu dažādās programmēšanas valodās.
Programma: Uzrakstiet programmu Shell šķirošanas ieviešanai C valodā.
#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;>