In diesem Artikel besprechen wir den Shell-Sortieralgorithmus. Shell-Sortierung ist die Verallgemeinerung der Einfügungssortierung, die die Nachteile der Einfügungssortierung überwindet, indem Elemente verglichen werden, die durch eine Lücke von mehreren Positionen getrennt sind.
Es handelt sich um einen Sortieralgorithmus, der eine erweiterte Version der Einfügungssortierung darstellt. Die Shell-Sortierung hat die durchschnittliche zeitliche Komplexität der Einfügungssortierung verbessert. Ähnlich wie bei der Einfügungssortierung handelt es sich um einen vergleichsbasierten und direkten Sortieralgorithmus. Die Shell-Sortierung ist für mittelgroße Datensätze effizient.
Bei der Einfügesortierung können Elemente jeweils nur um eine Position nach vorne verschoben werden. Um ein Element an eine weit entfernte Position zu bewegen, sind viele Bewegungen erforderlich, die die Ausführungszeit des Algorithmus erhöhen. Aber die Shell-Sortierung überwindet diesen Nachteil der Einfügungssortierung. Es ermöglicht auch die Bewegung und den Austausch weit entfernter Elemente.
Dieser Algorithmus sortiert zunächst die weit voneinander entfernten Elemente und verringert anschließend die Lücke zwischen ihnen. Diese Lücke wird als bezeichnet Intervall. Dieses Intervall kann mithilfe von berechnet werden Knuths Formel unten angegeben -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Sehen wir uns nun den Algorithmus der Shell-Sortierung an.
Algorithmus
Die einfachen Schritte zum Erreichen der Shell-Sortierung sind wie folgt aufgeführt:
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;>
Funktionsweise des Shell-Sortieralgorithmus
Sehen wir uns nun die Funktionsweise des Shell-Sortieralgorithmus an.
Um die Funktionsweise des Shell-Sortieralgorithmus zu verstehen, nehmen wir ein unsortiertes Array. Anhand eines Beispiels lässt sich die Shell-Sortierung leichter verstehen.
Die Elemente des Arrays seien -
Wir werden die ursprüngliche Reihenfolge der Shell-Sortierung verwenden, d. h. N/2, N/4, ..., 1 als Intervalle.
In der ersten Schleife ist n gleich 8 (Größe des Arrays), sodass die Elemente im Abstand von 4 liegen (n/2 = 4). Elemente werden verglichen und ausgetauscht, wenn sie nicht in Ordnung sind.
Hier, in der ersten Schleife, das Element an der 0ThDie Position wird mit dem Element bei 4 verglichenThPosition. Wenn die 0ThIst das Element größer, wird es mit dem Element bei 4 vertauschtThPosition. Ansonsten bleibt es gleich. Dieser Vorgang wird für die verbleibenden Elemente fortgesetzt.
Im Intervall von 4 sind die Unterlisten {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Jetzt müssen wir die Werte in jeder Unterliste vergleichen. Nach dem Vergleich müssen wir sie bei Bedarf im ursprünglichen Array austauschen. Nach dem Vergleich und Austausch sieht das aktualisierte Array wie folgt aus:
In der zweiten Schleife liegen die Elemente im Intervall 2 (n/4 = 2), wobei n = 8.
Jetzt nehmen wir das Intervall von 2 um den Rest des Arrays zu sortieren. Bei einem Intervall von 2 werden zwei Unterlisten generiert: {12, 25, 33, 40} und {17, 8, 31, 42}.
Jetzt müssen wir erneut die Werte in jeder Unterliste vergleichen. Nach dem Vergleich müssen wir sie bei Bedarf im ursprünglichen Array austauschen. Nach dem Vergleich und Austausch sieht das aktualisierte Array wie folgt aus:
In der dritten Schleife liegen die Elemente im Intervall 1 (n/8 = 1), wobei n = 8. Zuletzt verwenden wir das Intervall mit dem Wert 1, um die restlichen Elemente des Arrays zu sortieren. In diesem Schritt verwendet die Shell-Sortierung die Einfügungssortierung, um die Array-Elemente zu sortieren.
Jetzt wird das Array in aufsteigender Reihenfolge sortiert.
Komplexität der Shell-Sortierung
Sehen wir uns nun die zeitliche Komplexität der Shell-Sortierung im besten, durchschnittlichen und schlechtesten Fall an. Wir werden auch die räumliche Komplexität der Shell-Sortierung sehen.
1. Zeitkomplexität
| Fall | Zeitkomplexität |
|---|---|
| I'm besten fall | O(n*logn) |
| Durchschnittlicher Fall | O(n*log(n)2) |
| Schlimmsten Fall | An2) |
2. Raumkomplexität
| Weltraumkomplexität | O(1) |
| Stabil | NEIN |
- Die räumliche Komplexität der Shell-Sortierung beträgt O(1).
Implementierung der Shell-Sortierung
Sehen wir uns nun die Programme von Shell in verschiedenen Programmiersprachen an.
Programm: Schreiben Sie ein Programm zur Implementierung der Shell-Sortierung in der Sprache C.
#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;>