Сортування вставками.
Порівняння загальних характеристик роботи різних методів сортування
Будемо розбирати алгоритм, розглядаючи його дії на i-му кроці. Як говорилося вище, послідовність до цього моменту розділена на дві частини: готову a … a і невпорядковану a … a. Таким чином, в процесі вставки ми «просіваємо» елемент x до початку масиву, зупиняючись у випадку, коли знайдено елемент, менший x або досягнуто початок послідовності. В залежності від результату порівняння елемент або… Читати ще >
Сортування вставками. Порівняння загальних характеристик роботи різних методів сортування (реферат, курсова, диплом, контрольна)
Сортування простими вставками в чомусь схожа на вищевикладені методи.
Аналогічним чином робляться проходи по частині масиву, і аналогічним же чином на його початку «виростає» відсортована послідовність.
Однак у сортуванні бульбашкою або вибором можна було чітко заявити, що на i-му кроці елементи a [0] … a [i] стоять на правильних місцях і нікуди більше не перемістяться. Тут же подібне твердження буде більш слабким: послідовність a [0] … a [i] впорядкована. При цьому по ходу алгоритму в неї будуть вставлятися (див. назву методу) все нові елементи.
Будемо розбирати алгоритм, розглядаючи його дії на i-му кроці. Як говорилося вище, послідовність до цього моменту розділена на дві частини: готову a [0] … a [i] і невпорядковану a [i +1] … a [n].
На наступному, (i +1)-м кожному кроці алгоритму беремо a [i +1] і вставляємо на потрібне місце в готову частину масиву.
Пошук відповідного місця для чергового елемента вхідної послідовності здійснюється шляхом послідовних порівнянь з елементом, що стоять перед ним.
В залежності від результату порівняння елемент або залишається на поточному місці (вставка завершена), або вони міняються місцями і процес повторюється (Рис. 2.10).
Рисунок 2.10 — Процес сортування вставками.
Таким чином, в процесі вставки ми «просіваємо» елемент x до початку масиву, зупиняючись у випадку, коли знайдено елемент, менший x або досягнуто початок послідовності.
Аналогічно сортуванні вибором, середнє, а також найгірше число порівнянь і пересилань оцінюються як Theta (n2), додаткова пам’ять при цьому не використовується.
Хорошим показником сортування є дуже природна поведінка: майже відсортований масив, буде дуже швидко відсортовано. Це, вкупі зі стійкістю алгоритму, робить метод хорошим вибором у відповідних ситуаціях.
Алгоритм можна злегка поліпшити. Зауважимо, що на кожному кроці внутрішнього циклу перевіряються 2 умови. Можна об'єднати з в одне, поставивши в початок масиву спеціальний сторожовий елемент. Він повинен бути свідомо менше всіх інших елементів масиву. Тоді при j = 0 буде свідомо вірно a [0] = 0.
Таким чином, сортування відбуватиметься правильним чином, а у внутрішньому циклі стане на одне порівняння менше. З урахуванням того, що воно проводилося Theta (n2) раз, це — реальна перевага. Однак, відсортований масив буде не повний, так як з нього зникло перше число. Для закінчення сортування це число слід повернути назад, а потім вставити в відсортовану послідовність a [1] … a [n] (Рис. 2.11).
Рисунок 2.11 — Закінчення процесу сортування.