Алгоритъм за сортиране на Shell с ПРИМЕР
Какво е Shell Sort
Методът на Shell или сортирането на Shell в структурата на данните е ефективен алгоритъм за сортиране на място за сравнение. Той е кръстен на Доналд Шел, когато той предложи първоначалната идея през 1959 г. Shell sort е обобщено разширение на алгоритъма за сортиране чрез вмъкване.
Основната идея на този алгоритъм за сортиране е да групира елементите, които са далеч един от друг, и да ги сортира по съответния начин. След това постепенно намалете разстоянието между тях. Shell сортирането преодолява средната сложност на случая на сортиране чрез вмъкване чрез сравняване и обмен на елементи, които са далеч.
Тази празнина, известна като интервал, се редуцира според някои оптимални последователности на празнините. Времето за изпълнение на shell sort също зависи от тези последователности. Има няколко поредици от пропуски, като например оригиналната последователност на Шел, формулата на Кнут, увеличенията на Хибард и т.н. Оригиналната последователност от пропуски на Шел е – n/2, n/4, n/8, ……….1
Алгоритъм за сортиране на Shell
Стъпките или процедурата за алгоритъма за сортиране на обвивката е както следва-
Стъпка 1) Инициализирайте стойността на интервала, h = n/2. (В този пример n е размерът на масива)
Стъпка 2) Поставете всички елементи на разстояние от интервала h в подсписък.
Стъпка 3) Сортирайте тези подсписъци с помощта на сортиране чрез вмъкване.
Стъпка 4) Задайте нов интервал, h=h/2.
Стъпка 5) Ако h>0, отидете на стъпка 2. В противен случай отидете на стъпка 6.
Стъпка 6) Полученият резултат ще бъде сортираният масив.
Как работи Shell Sort
При сортиране чрез вмъкване елементите се преместват само с една позиция в даден момент. Напротив, shell сортирането разделя масива на по-малки части въз основа на стойността на интервала и изпълнява сортиране чрез вмъкване върху тези части.
Постепенно стойността на интервала намалява и размерът на разделените части се увеличава. Тъй като частите са индивидуално сортирани предварително, обединяването на тези части изисква по-малко стъпки от вмъкване сортиране.
Следният GIF показва демонстрация на сортиране на черупки. В тази демонстрация червената и синята показана стойност се сравняват и разменят въз основа на сортиране на вмъкване. След това интервалът намалява и shell сортирането инициира сортиране чрез вмъкване в тези почти сортирани данни.
Работа на алгоритъма за сортиране на Shell
Нека видим следния пример за алгоритъм за сортиране на обвивка. В този пример ще сортираме следния масив с помощта на shell sort:
Стъпка 1) Тук размерът на масива е 8. Така стойността на интервала ще бъде h = 8/2 или 4.
Стъпка 2) Сега ще съхраним всички елементи на разстояние 4. За нашия случай подсписъците са {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Стъпка 3) Сега тези подсписъци ще бъдат сортирани чрез сортиране чрез вмъкване, където се използва временна променлива за сравняване на числата и съответното сортиране.
Масивът ще бъде като следния след операциите за размяна -
Стъпка 4) Сега ще намалим първоначалната стойност на интервала. Новият интервал ще бъде h=h/2 или 4/2 или 2.
Стъпка 5) Тъй като 2>0, ще преминем към стъпка 2, за да съхраним всички елементи на разстояние 2. За това време подсписъците са-
{1, 5, 8, 7}, {4, 2, 6, 3}
След това тези подсписъци ще бъдат сортирани чрез сортиране чрез вмъкване. След сравняване и размяна на първия подсписък, масивът ще бъде следният.
След сортиране на втория подсписък, оригиналният масив ще бъде:
След това отново интервалът ще бъде намален. Сега интервалът ще бъде h=h/2 или 2/1 или 1. Следователно ще използваме алгоритъма за сортиране чрез вмъкване, за да сортираме модифицирания масив.
Следва стъпка по стъпка процедурно описание на сортиране чрез вмъкване.
Интервалът отново се разделя на 2. По това време интервалът става 0. Така че преминаваме към стъпка 6.
Стъпка 6) Тъй като интервалът е 0, масивът се сортира по това време. Сортираният масив е-
Псевдо-код
Start Input array an of size n for (interval = n / 2; interval & gt; 0; interval /= 2) for (i = interval; i & lt; n; i += 1) temp = a[i]; for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; temp; j -= interval) a[j] = a[j - interval]; a[j] = temp; End
Програма за сортиране на Shell в C/C++
Вход:
//Shell Sort Program in C/C++ #include <bits/stdc++.h> using namespace std; void ShellSort(int data[], int size) { for (int interval = size / 2; interval > 0; interval /= 2) { for (int i = interval; i < size; i += 1) { int temp = data[i]; int j; for (j = i; j >= interval && data[j - interval] > temp; j -= interval) { data[j] = data[j - interval]; } data[j] = temp; } } } int main() { int data[] = {8, 6, 7, 2, 1, 4, 5, 3}; int size = sizeof(data) / sizeof(data[0]); ShellSort(data, size); cout << "Sorted Output: \n"; for (int i = 0; i < size; i++) cout << data[i] << " "; cout << "\n"; }
Изход:
Sorted Output: 1 2 3 4 5 6 7 8
Shell Пример за сортиране в Python
Вход:
#Shell Sort Example in Python def ShellSort(data, size): interval = size // 2 while interval > 0: for i in range(interval, size): temp = data[i] j = i while j >= interval and data[j - interval] > temp: data[j] = data[j - interval] j -= interval data[j] = temp interval //= 2 data = [8, 6, 7, 2, 1, 4, 5, 3] ShellSort(data, len(data)) print('Sorted Output:') print(data)
Изход:
Sorted Output: [1, 2, 3, 4, 5, 6, 7, 8]
Приложения на Shell Sort
Ето важни приложения на Shell Sort:
- Shell sort се използва в Linux ядрото тъй като не използва стек за повиквания.
- Библиотеката uClibc използва сортиране на Shell.
- bzip2 компресорът използва Shell сортиране, за да спре превишаването на рекурсията.
Предимства и недостатъци на Shell Sort
Предимства | Недостатъци |
---|---|
Не е необходимо извикване на стек. | Не е ефективен за огромни размери на масиви. |
Лесно изпълнение. | Неефективен за широко разпространени елементи. |
Ефективен за по-малко разположени елементи. |
Анализ на сложността на сортирането на Shell
Времева сложност на Shell Sort
Времевата сложност на алгоритъма за сортиране на обвивката е O(n^2). Мотивите са следните:
За най-добрия сценарий общото количество тестове за всички интервали, когато масивът е бил предварително подреден, е равно на log n. Така сложността ще бъде O(n*log n).
За най-лошия сценарий, нека разгледаме масива, който се състои по такъв начин, че елементите изискват най-голям брой сравнения. Тогава всички елементи няма да бъдат сравнени и превключени до последната итерация. Следователно общите сравнения, необходими за крайното увеличение, са O(n^2).
В заключение, сложността на времето ще бъде
- Сложност в най-добър случай: O(n*log n)
- Средна сложност на случая: O(n*log n)
- Сложност в най-лошия случай: O(n^2)
Сложността на времето за изпълнение на shell сортирането силно зависи от използваните последователности за нарастване на пропуските. Въпреки това, най-добрата последователност на нарастване за сортиране на черупки все още не е известна.
Shell Sort Space Complexity
При този сорт за сравнение не се нуждаем от допълнително помощно пространство. Така пространствената сложност на този вид алгоритъм е O(1).