В тази статия ще обсъдим алгоритъма за сортиране на обвивката. Shell сортирането е обобщение на сортирането чрез вмъкване, което преодолява недостатъците на сортирането чрез вмъкване чрез сравняване на елементи, разделени с празнина от няколко позиции.
Това е алгоритъм за сортиране, който е разширена версия на сортирането чрез вмъкване. Shell сортирането подобри средната времева сложност на сортирането чрез вмъкване. Подобно на сортирането чрез вмъкване, това е алгоритъм за сортиране на място, базиран на сравнение. Shell сортирането е ефективно за средни по размер набори от данни.
При сортиране чрез вмъкване в даден момент елементите могат да бъдат преместени напред само с една позиция. За да преместите елемент в далечна позиция, са необходими много движения, които увеличават времето за изпълнение на алгоритъма. Но shell сортирането преодолява този недостатък на сортирането чрез вмъкване. Позволява движението и размяната и на отдалечени елементи.
Този алгоритъм първо сортира елементите, които са далеч един от друг, след което впоследствие намалява разстоянието между тях. Тази празнина се нарича като интервал. Този интервал може да се изчисли с помощта на на Кнут формула, дадена по-долу -
q2 месеца
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Сега нека видим алгоритъма за сортиране на обвивката.
Алгоритъм
Простите стъпки за постигане на сортирането на черупката са изброени както следва -
празнота 0
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
Сега нека видим работата на алгоритъма за сортиране на обвивката.
За да разберем работата на алгоритъма за сортиране на shell, нека вземем несортиран масив. Ще бъде по-лесно да разберете сортирането на черупката чрез пример.
Нека елементите на масива са -
Ще използваме оригиналната последователност от сортиране на черупки, т.е. N/2, N/4,....,1 като интервали.
В първия цикъл n е равно на 8 (размер на масива), така че елементите лежат на интервал от 4 (n/2 = 4). Елементите ще бъдат сравнени и разменени, ако не са в ред.
Тук, в първия цикъл, елементът при 0thпозицията ще бъде сравнена с елемента на 4thпозиция. Ако 0thелементът е по-голям, той ще бъде разменен с елемента на 4thпозиция. Иначе си остава същото. Този процес ще продължи за останалите елементи.
На интервал от 4 подсписъците са {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Сега трябва да сравним стойностите във всеки подсписък. След сравняване трябва да ги разменим, ако е необходимо в оригиналния масив. След сравняване и размяна актуализираният масив ще изглежда по следния начин -
Във втория цикъл елементите лежат на интервал от 2 (n/4 = 2), където n = 8.
конвертиране на низ в цяло число
Сега вземаме интервала от 2 за сортиране на останалата част от масива. С интервал от 2 ще бъдат генерирани два подсписъка - {12, 25, 33, 40} и {17, 8, 31, 42}.
Сега отново трябва да сравним стойностите във всеки подсписък. След сравняване трябва да ги разменим, ако е необходимо в оригиналния масив. След сравняване и размяна актуализираният масив ще изглежда по следния начин -
низ в java методи
В третия цикъл елементите лежат на интервал от 1 (n/8 = 1), където n = 8. Накрая използваме интервала със стойност 1, за да сортираме останалите елементи на масива. В тази стъпка shell сортирането използва сортиране чрез вмъкване, за да сортира елементите на масива.
Сега масивът е сортиран във възходящ ред.
Сложност на сортиране на Shell
Сега нека видим времевата сложност на сортирането на Shell в най-добрия случай, средния случай и най-лошия случай. Ще видим и космическата сложност на сортирането на Shell.
1. Времева сложност
| Случай | Времева сложност |
|---|---|
| Най-добър случай | O(n*logn) |
| Среден случай | O(n*log(n)2) |
| Най-лошия случай | На2) |
2. Космическа сложност
| Космическа сложност | О(1) |
| Стабилен | НЕ |
- Пространствената сложност на сортирането на Shell е O(1).
Внедряване на сортиране на Shell
Сега, нека видим програмите на Shell sort в различни езици за програмиране.
програма: Напишете програма за реализиране на Shell сортиране на език 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;>