, які зміщені на дві позиції. І, нарешті, упорядковуються всі сусідні елементи:
прохід 1 f d a c b e
прохід 2 c b a f d e
прохід 3 a b c e d f
отриманий результат abcdef
Алгоритм:
{сортування Шелла} Shell (var item: DataArray; count: integer); = 5;, j, k, s, m: integer;: array [1. t] of integer;: DataItem; [1]: = 9; h [2]: = 5; h [3]: = 3; h [4]: ​​= 2; h [5]: = 1; m: = 1 to t do: = h [m];: =-k; i: = k +1 to count do: = item [i];: = ik; s = 0 then: = - k;: = s +1 ; [s]: = x;; (x
end;;; {кінець сортування Шелла}
При поверхневому погляді на алгоритм не можна сказати, що він дає хороший результат і навіть те, що в результаті вийде відсортований масив. Однак, він дає і те й інше. Ефективність цього алгоритму пояснюється тим, що при кожному проході використовується відносно невелике число елементів або елементи масиву вже знаходяться у відносному порядку, а впорядкованість збільшується при кожному новому перегляді даних. p align="justify"> Відстані між порівнюваними елементами можуть змінюватися по-різному. Обов'язковим є лише те, що останній крок повинен дорівнювати одиниці. Наприклад, хороші результати дає послідовність кроків 9, 5, 3, 2, 1, яка використана в показаному вище прикладі. Слід уникати послідовностей ступеня двійки, які, як показують складні математичні викладки, знижують ефективність алгоритму сортування. (Проте, при використанні таких послідовностей кроків між порівнюваними елементами це сортування буде як і раніше працювати правильно). p align="justify"> Внутрішній цикл має дві умови перевірки. Умова "х 0" і "j <= count" необхідні для того, щоб запобігти виходу за межі масиву "item". Ця додаткова перевірка в деякій мірі погіршує сортування Шелла. Злегка змінені версії сортування Шелла використовують спеціальні керуючі елементи, які не є в дійсності частиною тієї інформації, яка повинна сортуватися. Керуючі елементи мають граничні для масиву даних значення, тобто найменше та найбільше значення. У цьому випадку не обов'язково виконувати перевірку на граничні значення. Однак, застосування таких керуючих елементів вимагає спеціальних знань про ту інформацію, яка сортується, і це знижує універсальність процедури сортування. p align="justify"> Аналіз сортування Шелла потребує вирішення деяких складних математичних задач. Час виконання сортування Шелла пропорційно n1.2 Ця залежність значно краще квадратичної залежності, якій підпорядковуються розглянуті раніше алгоритми сортування. Однак, перш ніж ви вирішите використовувати сортування Шелла, слід мати на увазі, що швидке сортування дає навіть ще кращі результати. p align="center"> 3. Впровадження
...
