Контрольная работа по "Высшей математике"

[pic 1][pic 2]

Що ж відбувається у середньому, коли масив заповнений числами у випадковому порядку? У цьому випадку математичне очікування кількості переміщень елементів дорівнюватиме половині від числа переміщень у гіршому випадку (кожен елемент у середньому переміщатиметься не до самого початку списку, а тільки до середини цього шляху), тобто математичне очікування числа переміщень буде дорівнює n(n+ 1)/4=O(n2).

     Ще одним яскравим прикладом алгоритму сортування Шелла може слугувати дана задача: нехай наведено список A = (32, 95, 16, 82, 24, 66, 35, 19, 75, 54, 40, 43, 93, 68) і виконується його сортування методом Шелла, а в якості значень d обрані: 5, 3, 1. На першому етапі сортуються підсписки A, складені з усіх елементів A, що різняться на 5 позицій, тобто підсписки A_{5,1} = (32, 66, 40), A_{5, 2} = (95, 35, 43) , A_{5, 3} = (16, 19, 93), A_{5, 4} = (82, 75, 68), A_{5, 5} = (24, 54).

[pic 3]

Рисунок 3 - Приклад№2 алгоритму сортуванням Шелла

      В отриманому списку на другому кроці знову сортуються підсписки з елементів, що віддаляються на 3 позиції. Процес завершується звичайним сортуванням вставками списку, що вийшов.

Сортування Шелла зараз рідко використовується у серйозних додатках. Він може бути реалізований за допомогою невеликого коду і не використовує стек викликів, в деяких реалізаціях функції QSort в стандартній бібліотеці C, спрямованих на вбудовувані системи, використовується замість швидкого сортування. Сортування Шелла, наприклад, використовується у бібліотеці uClibc. З тих же причин, реалізація цього алгоритму є в ядрі Linux. Сортування Шелла також може служити субалгоритмом інтроспективного роду, для сортування коротких під масивів і запобігти патологічному уповільненню, коли глибина рекурсії перевищує задану межу. Використовують цей принцип, наприклад, у компресорі bzip2.