Ebben a cikkben a shell-rendezési algoritmust tárgyaljuk. A shell rendezés a beszúrásos rendezés általánosítása, amely a beszúrásos rendezés hátrányait több pozíciós hézaggal elválasztott elemek összehasonlításával küszöböli ki.
Ez egy rendezési algoritmus, amely a beillesztési rendezés kiterjesztett változata. A shell-rendezés javította a beillesztési rendezés átlagos időbeli összetettségét. A beillesztési rendezéshez hasonlóan ez egy összehasonlításon alapuló és helyben történő rendezési algoritmus. A shell rendezés közepes méretű adatkészletek esetén hatékony.
A beszúrásos rendezésben az elemek egyszerre csak egy pozícióval mozgathatók előre. Egy elem távoli pozícióba való mozgatásához sok olyan mozgás szükséges, amelyek növelik az algoritmus végrehajtási idejét. De a shell rendezés kiküszöböli a beillesztési rendezés ezen hátrányát. Lehetővé teszi a távoli elemek mozgatását és cseréjét is.
Ez az algoritmus először az egymástól távol eső elemeket rendezi, majd csökkenti a köztük lévő távolságot. Ezt a rést ún intervallum. Ez az intervallum a következővel számítható ki Knuth-é az alábbi képlet -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Most pedig lássuk a shell-rendezés algoritmusát.
Algoritmus
A shell rendezés elérésének egyszerű lépései a következők:
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 rendezési algoritmus működése
Most pedig lássuk a shell-rendezési algoritmus működését.
A shell-rendezési algoritmus működésének megértéséhez vegyünk egy rendezetlen tömböt. Egy példán keresztül könnyebb lesz megérteni a shell rendezést.
Legyen a tömb elemei -
Intervallumként az eredeti shell rendezési sorrendet fogjuk használni, azaz N/2, N/4,....,1.
Az első ciklusban n egyenlő 8-cal (a tömb mérete), tehát az elemek 4-es intervallumban fekszenek (n/2 = 4). Az elemeket összehasonlítja és felcseréli, ha nincsenek rendben.
Itt az első ciklusban a 0-nál lévő elemthpozíciót a 4-es elemhez hasonlítjukthpozíció. Ha a 0thelem nagyobb, felcserélődik a 4-es elemmelthpozíció. Ellenkező esetben ugyanaz marad. Ez a folyamat folytatódik a többi elem esetében is.
A 4-es intervallumban az allisták a következők: {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Most minden allistában össze kell hasonlítanunk az értékeket. Összehasonlítás után szükség esetén fel kell cserélnünk őket az eredeti tömbben. Összehasonlítás és csere után a frissített tömb a következőképpen fog kinézni:
A második ciklusban az elemek 2-es intervallumban helyezkednek el (n/4 = 2), ahol n = 8.
Most az intervallumot vesszük 2 hogy rendezze a tömb többi részét. 2-es időközönként két allista jön létre – {12, 25, 33, 40} és {17, 8, 31, 42}.
Most ismét össze kell hasonlítanunk az egyes allisták értékeit. Összehasonlítás után szükség esetén fel kell cserélnünk őket az eredeti tömbben. Összehasonlítás és csere után a frissített tömb a következőképpen fog kinézni:
A harmadik ciklusban az elemek 1-es intervallumban helyezkednek el (n/8 = 1), ahol n = 8. Végül az 1-es értékű intervallumot használjuk a tömb többi elemének rendezésére. Ebben a lépésben a shell-rendezés beszúrási rendezést használ a tömbelemek rendezéséhez.
Most a tömb növekvő sorrendben van rendezve.
Shell rendezés összetettsége
Most lássuk a Shell-rendezés időbeli összetettségét a legjobb, az átlagos és a legrosszabb esetben. Látni fogjuk a Shell fajta térbeli összetettségét is.
1. Időbonyolultság
| Ügy | Idő összetettsége |
|---|---|
| Legjobb eset | O(n*logn) |
| Átlagos eset | O(n*log(n)2) |
| Legrosszabb esetben | Tovább2) |
2. A tér összetettsége
| A tér összetettsége | O(1) |
| Stabil | NEM |
- A Shell rendezés térkomplexitása O(1).
A Shell fajta megvalósítása
Most lássuk a Shell programjait különböző programozási nyelveken.
Program: Írjon programot a Shell rendezés megvalósítására C nyelven.
#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;>