Сортування оболонки

У цьому підручнику ви дізнаєтесь, як працює сортування оболонки. Крім того, ви знайдете робочі приклади сортування оболонки в C, C ++, Java та Python.

Сортування оболонки - це алгоритм, який спочатку сортує елементи далеко один від одного і послідовно зменшує інтервал між елементами, які потрібно сортувати. Це узагальнена версія сортування вставки.

У сортуванні оболонки елементи з певним інтервалом сортуються. Інтервал між елементами поступово зменшується залежно від використовуваної послідовності. Продуктивність сортування оболонки залежить від типу послідовності, що використовується для даного вхідного масиву.

Деякі з оптимальних послідовностей, що використовуються:

  • Оригінальна послідовність оболонки: N/2 , N/4 ,… , 1
  • Приріст Кнута: 1, 4, 13,… , (3k - 1) / 2
  • Приріст Седжвіка: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Приріст Гіббарда: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Приріст Папернова та Стасевича: 1, 3, 5, 9, 17, 33, 65,…
  • Пратт: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Як працює сортування оболонки?

  1. Припустимо, нам потрібно відсортувати наступний масив. Початковий масив
  2. Ми використовуємо вихідну послідовність оболонки (N/2, N/4,… 1) як інтервали в нашому алгоритмі.
    У першому циклі, якщо розмір масиву N = 8тоді, елементи, що лежать на інтервалі N/2 = 4, порівнюються та міняються місцями, якщо вони не в порядку.
    1. 0-й елемент порівнюється з 4-м елементом.
    2. Якщо 0-й елемент більше 4-го, тоді 4-й елемент спочатку зберігається у tempзмінній, а 0thелемент (тобто більший елемент) зберігається в 4thпозиції, а елемент, що зберігається в temp, зберігається в 0thпозиції. Переставити елементи з інтервалом n / 2
      Цей процес триває для всіх інших елементів. Переставити всі елементи з інтервалом n / 2
  3. У другому циклі N/4 = 8/4 = 2береться інтервал і знову сортуються елементи, що лежать через ці інтервали. Переставляйте елементи з інтервалом n / 4.
    На цьому етапі ви можете заплутатися. Порівнюються всі елементи масиву, що лежать на поточному інтервалі. Порівнюються
    елементи на 4 і 2ndпозиції. 0thТакож порівнюються елементи на 2-му та позиційному. Порівнюються всі елементи масиву, що лежать на поточному інтервалі.
  4. Той самий процес триває для інших елементів. Переставити всі елементи з інтервалом n / 4
  5. Нарешті, коли інтервал дорівнює N/8 = 8/8 =1, сортуються елементи масиву, що лежать на інтервалі 1. Тепер масив повністю відсортований. Переставити елементи з інтервалом n / 8

Алгоритм сортування оболонки

 shellSort (масив, розмір) для інтервалу i <- size / 2n до 1 для кожного інтервалу "i" в масиві сортувати всі елементи в інтервалі "i" end shellSort

Приклади Python, Java та C / C ++

Python Java C C ++ 
# Shell sort in python def shellSort(array, n): # Rearrange elements at each n/2, n/4, n/8,… intervals interval = n // 2 while interval> 0: for i in range(interval, n): temp = array(i) j = i while j>= interval and array(j - interval)> temp: array(j) = array(j - interval) j -= interval array(j) = temp interval //= 2 data = (9, 8, 3, 7, 5, 6, 4, 1) size = len(data) shellSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Shell sort in Java programming import java.util.Arrays; // Shell sort class ShellSort ( // Rearrange elements at each n/2, n/4, n/8,… intervals void shellSort(int array(), int n) ( for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 8, 3, 7, 5, 6, 4, 1 ); int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) ) 
// Shell Sort in C programming #include // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); printf("Sorted array: "); printArray(data, size); ) 
// Shell Sort in C++ programming #include using namespace std; // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); cout << "Sorted array: "; printArray(data, size); )

Складність

Сортування оболонки - це нестабільний алгоритм сортування, оскільки цей алгоритм не досліджує елементи, що лежать між інтервалами.

Складність часу

  • Складність найгіршого випадку : менше або дорівнює Складність найгіршого випадку для сортування оболонки завжди менше або дорівнює . Згідно з теоремою Poonen, в гіршому випадку складність для роду оболочечной або або або що - то між ними.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Складність найкращого випадку : O(n*log n)
    коли масив уже відсортовано, загальна кількість порівнянь для кожного інтервалу (або приросту) дорівнює розміру масиву.
  • Середня складність справи : O(n*log n)
    вона близько .O(n1.25)

Складність залежить від обраного інтервалу. Вищевказані складності відрізняються для різних обраних послідовностей приросту. Найкраща послідовність приросту невідома.

Складність простору:

Складність простору для сортування оболонки становить O(1).

Додатки для сортування оболонки

Сортування оболонки використовується, коли:

  • виклик стека - накладні витрати. Бібліотека uClibc використовує цей сорт.
  • рекурсія перевищує межу. використовує компресор bzip2.
  • Сортування вставки погано працює, коли близькі елементи знаходяться далеко один від одного. Сортування оболонки допомагає зменшити відстань між закритими елементами. Таким чином, буде менше заміни, яку слід виконати.

Цікаві статті...