ісця за один прохід, а елемент, розташований на початку масиву (наприклад, елемент "d"), дуже повільно досягає свого місця. Необов'язково всі перегляди робити в одному напрямку. Замість цього всякий подальший перегляд можна робити в протилежному напрямку. У цьому випадку сильно віддалені від свого місця елементи швидко переміщатися в відповідне місце. Хоча це сортування є поліпшенням бульбашковим методом, її не можна рекомендувати для використання, оскільки час виконання як і раніше залежить квадратично від числа елементів. Число порівнянь не змінюється, а число обмінів зменшується лише на незначну величину.
В· Метод Шелла. p> Загальний метод, який використовує сортування вставкою, застосовує принцип зменшення відстані між порівнюваними елементами. Спочатку упорядковано всі елементи, які зміщені один від одного на три позиції. Потім сортуються всі елементи, які зміщені на дві позиції. І, нарешті, упорядковуються всі сусідні елементи. p> При поверхневому погляді на алгоритм не можна сказати, що він дає хороший результат і навіть те, що в результаті вийде відсортований масив. Однак, він дає і те й інше. Ефективність цього алгоритму пояснюється тим, що при кожному проході використовується відносно невелике число елементів або елементи масиву вже знаходяться у відносному порядку, а впорядкованість збільшується при кожному новому перегляді даних.
Відстані між порівнюваними елементами можуть змінюватися по-різному. Обов'язковим є лише те, що останній крок повинен дорівнювати одиниці. Наприклад, хороші результати дає послідовність кроків 9, 5, 3, 2, 1, яка використана в даній курсовій роботі. Слід уникати послідовностей ступеня двійки, які, як показують складні математичні викладки, знижують ефективність алгоритму сортування. /Однак, при використанні таких послідовностей кроків між порівнюваними елементами це сортування буде як і раніше працювати правильно. Злегка змінені версії сортування Шелла використовують спеціальні керуючі елементи, які не є в дійсності частиною тієї інформації, яка повинна сортуватися. Керуючі елементи мають граничні для масиву даних значення, тобто найменше та найбільше значення. У цьому випадку не обов'язково виконувати перевірку на граничні значення. Однак, застосування таких керуючих елементів вимагає спеціальних знань про ту інформації, яка сортується, і це знижує універсальність процедури сортування. Аналіз сортування Шелл потребує вирішення деяких складних математичних задач. Час виконання сортування Шелла пропорційно n ** 1.2. Ця залежність значно краще квадратичної залежності, якій підпорядковуються розглянуті раніше алгоритми сортування. Однак, перш ніж ви вирішите використовувати сортування Шелла, слід мати на увазі, що швидке сортування дає навіть ще кращі результати.
У розглянутих алгоритмах сортування запис переміщається щоразу тільки на одну позицію. При цьому середній час роботи буде в кращому випадку пропорційно n. Методом, істотно перевершує прості вставки, при якому записи переміщаються великими стрибками, є метод Шелла (сортування з убутним кроком). Метод полягає в тому, що впорядкований масив поділяється на групи елементів, кожна з яких упорядковується методом вставки. У процесі упорядкування розміри таких груп збільшуються до тих пір, поки всі елементи масиву не увійдуть у впорядковану групу. Вибір черговий впорядковує групи і її розташування всередині масиву виробляються так, щоб можна було використовувати попередню впорядкованість. Групою масиву називають послідовність елементів, номери яких утворюють арифметичну прогресію з різницею h (h називають кроком групи). На початку процесу впорядкування вибирається перший крок групи h1, який залежить від розміру таблиці. Шелл запропонував брати
h1 = [n/2], а hi = h ((i-1)/2).
У більш пізніх роботах Хиббард показав, що для прискорення процесу доцільно визначити крок h1 за формулою:
h1 = 2 ** k +1, де 2 ** k Після вибору h1 методом вставки упорядковуються групи, містять елементи з номерами позицій
i, i + h1, i +2 * h1, ..., i + mi * h1.
При цьому i = 1,2, ..., h1; m [i] - найбільше ціле, яке задовольняє нерівності i + m [i] * hi <= n.
Потім вибирається крок h2
h2> ...> hl). Цей останній етап являє собою впорядкування всього масиву методом вставки. Але так як вихідний масив впорядковує окремими групами з послідовним об'єднанням цих груп, то загальна кількість порівнянь значно менше, ніж n/4, необхідну при методі вставки. Число операцій порівняння пропорційно n * (log2 (n)) ** 2.
В· Обмінна сортування з розділенням (Quicksort).
Даний метод є одним з кращих методів внутрішньої сортування і вельми ефекти...
