U ovom ćemo članku raspravljati o algoritmu sortiranja ljuske. Shell sortiranje je generalizacija sortiranja umetanjem, koje prevladava nedostatke sortiranja umetanjem usporedbom elemenata odvojenih razmakom od nekoliko pozicija.
To je algoritam sortiranja koji je proširena verzija sortiranja umetanjem. Shell sort je poboljšao prosječnu vremensku složenost sortiranja umetanjem. Kao sličan sortiranju umetanjem, to je algoritam za sortiranje na mjestu koji se temelji na usporedbi. Shell sortiranje učinkovito je za skupove podataka srednje veličine.
U sortiranju umetanjem, elementi se mogu pomaknuti unaprijed samo za jednu poziciju. Da bi se element pomaknuo na daleku poziciju, potrebno je mnogo pokreta koji povećavaju vrijeme izvršenja algoritma. Ali shell sortiranje prevladava ovaj nedostatak sortiranja umetanjem. Također omogućuje pomicanje i izmjenu udaljenih elemenata.
Ovaj algoritam prvo razvrstava elemente koji su udaljeni jedan od drugoga, a potom smanjuje razmak između njih. Taj se jaz naziva kao interval. Taj se interval može izračunati pomoću Knuthova formula navedena u nastavku -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Sada, da vidimo algoritam sortiranja ljuske.
Algoritam
Jednostavni koraci za postizanje sortiranja ljuske navedeni su kako slijedi -
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;>
Rad Shell algoritma sortiranja
Sada, da vidimo kako radi algoritam za sortiranje ljuske.
Da bismo razumjeli rad algoritma sortiranja ljuske, uzmimo nesortirani niz. Razvrstavanje ljuski bit će lakše razumjeti na primjeru.
Neka su elementi niza -
Kao intervale koristit ćemo izvorni niz shell sortiranja, tj. N/2, N/4,....,1.
U prvoj petlji, n je jednako 8 (veličina niza), tako da elementi leže u intervalu od 4 (n/2 = 4). Elementi će se usporediti i zamijeniti ako nisu u redu.
npm očisti predmemoriju
Ovdje, u prvoj petlji, element na 0thpozicija će se uspoređivati s elementom na 4thpoložaj. Ako je 0thelement veći, bit će zamijenjen elementom na 4thpoložaj. Inače, ostaje isto. Ovaj proces će se nastaviti za preostale elemente.
U intervalu od 4, podliste su {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Sada moramo usporediti vrijednosti u svakoj pod-listi. Nakon usporedbe, moramo ih zamijeniti ako je potrebno u izvornom nizu. Nakon usporedbe i zamjene, ažurirani niz će izgledati kako slijedi -
U drugoj petlji elementi leže u intervalu od 2 (n/4 = 2), gdje je n = 8.
Sada uzimamo interval od 2 za sortiranje ostatka niza. S intervalom od 2, bit će generirana dva podlista - {12, 25, 33, 40} i {17, 8, 31, 42}.
Sada opet moramo usporediti vrijednosti u svakoj pod-listi. Nakon usporedbe, moramo ih zamijeniti ako je potrebno u izvornom nizu. Nakon usporedbe i zamjene, ažurirani niz će izgledati kako slijedi -
U trećoj petlji elementi leže u intervalu od 1 (n/8 = 1), gdje je n = 8. Na kraju koristimo interval vrijednosti 1 za sortiranje ostalih elemenata niza. U ovom koraku sortiranje ljuske koristi sortiranje umetanjem za sortiranje elemenata niza.
Sada je niz poredan uzlaznim redoslijedom.
Složenost sortiranja ljuske
Pogledajmo sada vremensku složenost Shell sortiranja u najboljem slučaju, prosječnom slučaju i najgorem slučaju. Također ćemo vidjeti kompleksnost prostora Shell sorte.
1. Vremenska složenost
| Slučaj | Vremenska složenost |
|---|---|
| Najbolji slučaj | O(n*log) |
| Prosječan slučaj | O(n*log(n)2) |
| Najgori slučaj | Na2) |
2. Složenost prostora
| Složenost prostora | O(1) |
| Stabilan | NE |
- Prostorna složenost Shell sortiranja je O(1).
Implementacija Shell sortiranja
Pogledajmo sada programe Shell sortiranja u različitim programskim jezicima.
usporedba nizova java
Program: Napišite program za implementaciju Shell sortiranja u C jeziku.
#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;>