] сортується допомогою приміщення a [ i ] в підходящу позицію серед уже відсортованих елементів:
Також як і при сортуванні вибором, у процесі сортування елементи ліворуч від вказівника i знаходяться вже в сортованому порядку, але вони не обов'язково знаходяться у своїй останній позиції, оскільки їх ще можуть пересунути направо щоб вставити більш маленькі елементи зустрінуті пізніше. Масив стає повністю сортували коли покажчик досягає правого краю.
Проте є ще одна важлива деталь: програма insertion не завжди працює, оскільки while може проскочити за лівий край масиву, коли v - самий менший елемент масиву. Щоб виправити ситуацію, ми поміщаємо В«сторожовийВ» ключ у a [0], роблячи його, по крайней мере, не більше, ніж найменший ключ масиву. Сторожові елементи повсюдно використовуються в ситуаціях подібних до цієї для запобігання додаткової перевірки (у даному випадку j > 0), що майже завжди допомагає у внутрішніх циклах.
Бульбашкова сортування
Елементарний метод сортування, який часто дають на вступних заняттях - це бульбашкова сортування : Ті, що стоять поруч елементи масиву обмінюються місцями, до тих пір, поки зустрічаються несортовані пари. Реалізація цього методу дана нижче. p> Щоб повірити в те, що вона насправді працює, може знадобитися деякий час. Для цього зауважте, що коли під час першого проходу ми зустрічаємо максимальний елемент, ми обмінюємо його з кожним елементом праворуч від нього поки він не опиниться в крайній правою позиції. На другому проході ми поміщаємо другий максимальний елемент у передостанню позицію і так далі. Бульбашкова сортування працює також як і сортування вибором, хоча вона і робить набагато більше роботи на те, щоб перемістити елемент у його кінцеву позицію.
Характеристики найпростіших сортувань
Властивість 1 Сортування вибором використовує близько порівнянь і N обмінів.
Властивість 2 Сортування вставкою використовує близько порівнянь і обмінів у середньому, і в два рази більше в найгіршому випадку.
Властивість 3 Бульбашкова сортування використовує близько порівнянь і обмінів у середньому і найгіршому випадках.
Властивість 4 Сортування вставкою лінійна для В«майже сортованихВ» файлів.
Властивість 5 Сортування вибором лінійна для файлів з великими записами і маленькими ключами.
Сортування файлів з великими записами
Дуже часто буває можливо (і бажано) зробити так, щоб при сортуванні файлу складається з N елементів будь-якому методом було б зроблено тільки N операцій обміну повного запису допомогою непрямої адресації до елементів масиву (використовуючи масив індексів або покажчиків), а саму реорганізацію робити після.
Більш конкретно: якщо масив a [1 .. N] містить великі записи, то ми віддамо перевагу використовувати масив покажчиків p [1 .. N] для того, щоб знати, де знаходиться черговий елемент масиву a, і для твору псевдообмена. Нижче наведена програма сортування вставкою з використанням масиву покажчиків:
Для запобігання зайвого контролю в циклі, в програмі знову використовуються В«сторожовіВ» елементи.
Спочатку, індекси йдуть по порядку. Потім порядок індексів починає змінюватися так, щоб масив a, прочитаний по порядку читання індексів був упорядкований.
Для цього ми можемо використовувати наступну процедуру, яка фізично впорядковує запису файлу використовуючи при цьому N перестановок:
Сортування Шелла
Сортування вставкою працює повільно тому, що вона обмінює тільки суміжні елементи. Оболочечная сортування є найпростішим розширенням сортування вставкою, яка збільшує швидкість роботи алгоритму за рахунок того, що дозволяє обмінювати елементи знаходяться далеко один від одного.
Основна ідея алгоритму полягає в тому, щоб відсортувати всі групи файлу складаються з елементів файлу віддалених один від одного на відстань h. Такі файли називаються h-сортованими. Коли ми h-сортуємо файл по деякому великому h, ми пересуваємо його елементи на великі відстані. Це полегшує роботу сортування для менших значень h. Процес закінчується коли h зменшується до 1. p> Наведена програма використовує послідовність ... 1093, 364, 121, 40, 13, 4, 1. Можуть існувати й інші послідовності - одні краще, інші гірше.
Властивість 6 Оболочечная сортування ніколи не робить більш ніж N1.5 порівнянь для вищевказаної послідовності h.
Підрахунок розподілу
У багатьох випадках ми знаємо, що значення ключів у файлі лежать в яких або межах. У цих ситуаціях застосуємо алгоритм, іменований підрахунок розподілу. Тут наведена програма для цього простого алгоритму. br/>
