W tym artykule omówimy algorytm sortowania powłoki. Sortowanie powłokowe to uogólnienie sortowania przez wstawianie, które przezwycięża wady sortowania przez wstawianie, porównując elementy oddzielone odstępem kilku pozycji.
Jest to algorytm sortowania będący rozszerzoną wersją sortowania przez wstawianie. Sortowanie powłokowe poprawiło średni czas złożoności sortowania przez wstawianie. Podobnie jak sortowanie przez wstawianie, jest to algorytm sortowania lokalnego i oparty na porównaniu. Sortowanie powłokowe jest efektywne w przypadku zbiorów danych średniej wielkości.
Podczas sortowania przez wstawianie elementy można przesuwać w przód tylko o jedną pozycję. Aby przesunąć element w odległą pozycję, wymaganych jest wiele ruchów, które wydłużają czas wykonania algorytmu. Ale sortowanie powłokowe eliminuje tę wadę sortowania przez wstawianie. Umożliwia także przemieszczanie i zamianę odległych elementów.
Algorytm ten najpierw sortuje elementy oddalone od siebie, a następnie zmniejsza odstęp między nimi. Ta luka nazywa się interwał. Przedział ten można obliczyć za pomocą Knutha wzór podany poniżej -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Przyjrzyjmy się teraz algorytmowi sortowania przez powłokę.
Algorytm
Proste kroki prowadzące do sortowania powłoki są następujące:
lista
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;>
Działanie algorytmu sortowania powłoki
Przyjrzyjmy się teraz działaniu algorytmu sortowania przez powłokę.
Aby zrozumieć działanie algorytmu sortowania powłoki, weźmy nieposortowaną tablicę. Sortowanie powłoki będzie łatwiejsze do zrozumienia na przykładzie.
Niech elementami tablicy są -
dopełnianie CSS
Jako przedziały użyjemy oryginalnej sekwencji sortowania powłokowego, tj. N/2, N/4,.....,1.
W pierwszej pętli n jest równe 8 (rozmiar tablicy), więc elementy leżą w odstępie 4 (n/2 = 4). Elementy zostaną porównane i zamienione, jeżeli nie będą ułożone w odpowiedniej kolejności.
Tutaj, w pierwszej pętli, element na poziomie 0tpozycja zostanie porównana z elementem na 4tpozycja. Jeśli 0telement jest większy, zostanie zamieniony z elementem o wartości 4tpozycja. W przeciwnym razie pozostaje takie samo. Proces ten będzie kontynuowany dla pozostałych elementów.
W przedziale 4 podlisty to {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Teraz musimy porównać wartości na każdej podliście. Po porównaniu musimy je zamienić, jeśli jest to wymagane, w oryginalnej tablicy. Po porównaniu i zamianie zaktualizowana tablica będzie wyglądać następująco:
W drugiej pętli elementy leżą w odstępie 2 (n/4 = 2), gdzie n = 8.
Teraz bierzemy przedział 2 aby posortować resztę tablicy. W odstępie 2 zostaną wygenerowane dwie podlisty - {12, 25, 33, 40} i {17, 8, 31, 42}.
przekonwertuj ciąg na liczbę całkowitą
Teraz ponownie musimy porównać wartości na każdej podliście. Po porównaniu musimy je zamienić, jeśli jest to wymagane, w oryginalnej tablicy. Po porównaniu i zamianie zaktualizowana tablica będzie wyglądać następująco:
W trzeciej pętli elementy leżą w odstępie 1 (n/8 = 1), gdzie n = 8. Na koniec używamy przedziału o wartości 1 do sortowania pozostałych elementów tablicy. W tym kroku sortowanie powłokowe wykorzystuje sortowanie przez wstawianie do sortowania elementów tablicy.
Teraz tablica jest posortowana rosnąco.
Złożoność sortowania powłoki
Przyjrzyjmy się teraz złożoności czasowej sortowania Shella w najlepszym przypadku, średnim i najgorszym przypadku. Zobaczymy także złożoność przestrzenną sortowania powłoki.
1. Złożoność czasowa
| Sprawa | Złożoność czasu |
|---|---|
| Najlepszy przypadek | O(n*log) |
| Przeciętny przypadek | O(n*log(n)2) |
| Najgorszy przypadek | NA2) |
2. Złożoność przestrzeni
| Złożoność przestrzeni | O(1) |
| Stabilny | NIE |
- Złożoność przestrzenna sortowania powłoki wynosi O (1).
Implementacja sortowania powłoki
Przyjrzyjmy się teraz programom Shella sortowanym w różnych językach programowania.
Program: Napisz program realizujący sortowanie powłoki w języku 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;>