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