Šiame straipsnyje aptarsime apvalkalo rūšiavimo algoritmą. Shell sort yra įterpimo rūšiavimo apibendrinimas, kuris pašalina įterpimo rūšiavimo trūkumus, lyginant elementus, atskirtus kelių pozicijų tarpu.
Tai rūšiavimo algoritmas, kuris yra išplėstinė įterpimo rūšiavimo versija. Shell rūšiavimas pagerino vidutinį įterpimo rūšiavimo laiko sudėtingumą. Kaip panašus į įterpimo rūšiavimą, tai yra palyginimu pagrįstas rūšiavimo vietoje algoritmas. Shell rūšiavimas yra efektyvus vidutinio dydžio duomenų rinkiniams.
Įterpimo rūšiavimo metu elementai vienu metu gali būti perkeliami į priekį tik viena pozicija. Norint perkelti elementą į tolimą padėtį, reikia atlikti daug judesių, kurie padidina algoritmo vykdymo laiką. Tačiau apvalkalo rūšiavimas įveikia šį įterpimo rūšiavimo trūkumą. Tai taip pat leidžia judėti ir keisti tolimus elementus.
Šis algoritmas pirmiausia surūšiuoja elementus, kurie yra toli vienas nuo kito, o vėliau sumažina tarpą tarp jų. Ši spraga vadinama kaip intervalas. Šį intervalą galima apskaičiuoti naudojant Knutho žemiau pateikta formulė -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Dabar pažiūrėkime į apvalkalo rūšiavimo algoritmą.
Algoritmas
Paprasti apvalkalo rūšiavimo pasiekimo veiksmai yra išvardyti taip:
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“ rūšiavimo algoritmo veikimas
Dabar pažiūrėkime, kaip veikia apvalkalo rūšiavimo algoritmas.
Norėdami suprasti apvalkalo rūšiavimo algoritmo veikimą, paimkime nerūšiuotą masyvą. Per pavyzdį bus lengviau suprasti apvalkalo rūšiavimą.
Tegul masyvo elementai yra -
Kaip intervalus naudosime pradinę apvalkalo rūšiavimo seką, ty N/2, N/4,....,1.
Pirmoje kilpoje n yra lygus 8 (masyvo dydis), taigi elementai yra 4 intervale (n/2 = 4). Elementai bus lyginami ir sukeisti, jei jie nėra tvarkingi.
Čia, pirmoje kilpoje, elementas ties 0thpadėtis bus lyginama su 4 elementuthpadėtis. Jei 0thelementas yra didesnis, jis bus pakeistas 4 elementuthpadėtis. Priešingu atveju jis lieka toks pat. Šis procesas bus tęsiamas su likusiais elementais.
4 intervalu posąraščiai yra {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Dabar turime palyginti kiekvieno sąrašo reikšmes. Palyginę, turime juos pakeisti, jei reikia, pradiniame masyve. Palyginus ir sukeitus, atnaujintas masyvas atrodys taip -
Antroje kilpoje elementai yra 2 intervale (n/4 = 2), kur n = 8.
java masyvo sąrašas
Dabar mes laikome intervalą 2 norėdami surūšiuoti likusią masyvo dalį. Su 2 intervalu bus sugeneruoti du posąraščiai – {12, 25, 33, 40} ir {17, 8, 31, 42}.
Dabar vėl turime palyginti reikšmes kiekviename posąraše. Palyginę, turime juos pakeisti, jei reikia, pradiniame masyve. Palyginus ir sukeitus, atnaujintas masyvas atrodys taip -
Trečiojoje kilpoje elementai yra 1 intervale (n/8 = 1), kur n = 8. Pagaliau mes naudojame 1 reikšmės intervalą likusiems masyvo elementams surūšiuoti. Šiame veiksme apvalkalo rūšiavimas naudoja įterpimo rūšiavimą masyvo elementams rūšiuoti.
Dabar masyvas rūšiuojamas didėjančia tvarka.
Korpuso rūšiavimo sudėtingumas
Dabar pažiūrėkime „Shell“ rūšiavimo sudėtingumą geriausiu, vidutiniu ir blogiausiu atveju. Taip pat pamatysime „Shell“ rūšiavimo erdvės sudėtingumą.
1. Laiko sudėtingumas
| Byla | Laiko sudėtingumas |
|---|---|
| Geriausias atvejis | O (n*logn) |
| Vidutinis atvejis | O(n*log(n)2) |
| Blogiausiu atveju | O (n2) |
2. Erdvės sudėtingumas
| Erdvės sudėtingumas | O(1) |
| Stabilus | NE |
- „Shell“ rūšiavimo erdvės sudėtingumas yra O(1).
Shell rūšiavimo įgyvendinimas
Dabar pažiūrėkime, kaip Shell programos rūšiuojamos skirtingomis programavimo kalbomis.
Programa: Parašykite programą, kuri įdiegtų Shell sort C kalba.
#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;>