Елементарні методи сортування
В якості нашої першої екскурсії в область алгоритмів сортування, ми вивчимо деякі В«елементарніВ» методи які добре працюють для невеликих файлів або файлів спеціальної структури. Існує кілька причин, за якими бажано вивчення цих простих методів. По-перше, вони дають нам відносно безболісний спосіб вивчити термінологію і основні механізми роботи алгоритмів сортування, що дозволяє отримати необхідну базу для вивчення більш складних алгоритмів. По-друге, для багатьох завдань сортування буває краще використовувати прості методи, чим більш складні алгоритми. І, нарешті, деякі з простих методів можна розширити до більш хороших методів або використовувати їх для поліпшення більш складних.
У деяких програмах сортування краще використовувати прості алгоритми. Програми сортування часто використовуються тільки один раз (або кілька разів). Якщо кількість елементів, які потрібно відсортувати не велика (скажімо менше ніж 500 елементів), то може статися, що використання простого алгоритму буде більш ефективно, ніж розробка та налагодження складного алгоритму. Елементарні методи завжди придатні для маленьких файлів (скажімо менших, ніж 50 елементів); малоймовірно, що складний алгоритм було б розумно використовувати для таких файлів, якщо звичайно не потрібно сортувати велику кількість таких файлів.
Як правило, елементарні методи, які ми будемо обговорювати, виробляють близько операцій для сортування N довільно взятих елементів. Якщо N досить мало, то це може і не бути проблемою, і якщо елементи розподілені НЕ довільним чином, то ці алгоритми можуть працювати навіть швидше, ніж складні. Однак слід запам'ятати те, що ці алгоритми не слід використовувати для великих, довільно впорядкованих файлів, з одним єдиним винятком для алгоритму оболочечной сортування, який часто використовується в багатьох програмах.
Правила Ігри
Перед тим, як розглядати який-небудь конкретний алгоритм, було б корисно вивчити термінологію і деякі основні угоди про алгоритми сортування. Ми будемо вивчати алгоритми для сортування файлів записів містять ключі . Ключі, які є тільки частиною запису (часто дуже маленькою їх частиною), використовуються для управління процесом сортування. Метою алгоритму сортування є переорганізація записів у файлі так, щоб вони розташовувалися в ньому в деякому строго певному порядку (Звичайно в алфавітному або числовому). p> Якщо сортований файл цілком поміщається в пам'ять (або цілком поміщається в масив), то для нього ми використовуємо внутрішні методи сортування. Сортування даних з стрічки або диска називається зовнішньої сортуванням. Головна відмінність між ними полягає в тому, що при внутрішній сортуванні будь-який запис легко доступна, в той час як при зовнішній сортуванні ми можемо користуватися записами тільки послідовно, або великими блоками. Більшість алгоритмів сортування, які ми розглянемо - внутрішні.
Зазвичай, головне, що буде нас цікавити в алгоритмі - це час його роботи. Перші чотири алгоритму, які ми розглянемо, для сортування N елементів мають час роботи пропорційне, в той час як більш складні алгоритми використовують час пропорційне. (Можна показати, що ніякої алгоритм сортування не може використовувати менш, ніж порівнянь між ключами.) Після вивчення простих методів ми розглянемо більш складні методи, час роботи яких пропорційно і методи використовують бінарні властивості ключів для зменшення загального часу роботи до N.
Кількість використовуваної додаткової пам'яті алгоритму сортування - це ще один важливий фактор, який ми будемо брати до уваги. Взагалі кажучи, методи сортування діляться на три типи:
В· методи сортування, які сортують без використання додаткової пам'яті, за винятком, можливо, невеликого стека і/або масиву;
В· методи, які використовують для сортування зв'язані списки і тому використовують N додаткових покажчиків зберігаються в пам'яті;
В· і методи, які потребують додаткової пам'яті для зберігання копії сортованого файлу.
Стабільність - ще одна важлива характеристика методів сортування. Метод сортування називається стабільним, якщо він зберігає відносних порядок проходження записів з однаковими ключами. Наприклад, якщо алфавітний список групи сортується за оцінками, то стабільний метод створює список, в якому прізвища студентів з однаковими оцінками будуть впорядковані за алфавітом, а нестабільний метод створить список в якому, можливо, вихідний порядок буде порушений. Більшість простих методів стабільні, у той час як більшість добре відомих складних методів - ні. Якщо стабільність необхідна, то вона може бути досягнута за допомогою додавання до ключа невеликого індексу перед сортуванням або за допомогою подовження, будь-яким чином, ключа. Стабільність з легкістю приймається за норму; до нестабільності люди ставляться з не...
