Ноу Інти, лекція, сортування масивів
завдання сортування
Ця лекція присвячена суто алгоритмічної проблеми впорядкування даних.
Необхідність впорядкувати будь-які величини виникає в програмуванні дуже часто. Наприклад, вхідні дані подаються "упереміш", а вашій програмі зручніше обробляти впорядковану послідовність. Існують ситуації, коли попередня сортування даних дозволяє скоротити змістовну частину алгоритму в рази, а час його роботи - в десятки разів.
Однак вірно і зворотне. Наскільки б хорошим і ефективним не був обраний вами алгоритм. але якщо в якості підзадачі він використовує "погану" сортування, то вся робота по його оптимізації не буде корисною. Невдало реалізована сортування вхідних даних здатна помітно знизити ефективність алгоритму в цілому.
Методи впорядкування поділяються на внутрішні (обробні масиви) і зовнішні (що займаються тільки файлами) 1 Більш детальну інформацію про різні алгоритми впорядкування дивіться в книзі Дональда Кнута "Мистецтво програмування ЕОМ", том 3: "Сортування і пошук".
Цю лекцію ми присвятимо тільки внутрішнім сортувань. Їх важлива особливість полягає в тому, що ці алгоритми не вимагають додаткової пам'яті: вся робота з упорядкування проводиться всередині одного і того ж масиву.
прості сортування
До простих внутрішнім сортувань відносять методи, складність яких пропорційна квадрату розмірності вхідних даних. Іншими словами, при сортуванні масиву. що складається з N компонент. такі алгоритми будуть виконувати С * N 2 дій, де С - деяка константа.
Кількість дій, необхідних для впорядкування деякої послідовності даних, звичайно ж, залежить не тільки від довжини цієї послідовності, але і від її структури. Наприклад, якщо на вхід подається вже впорядкована послідовність (про що програма. Зрозуміло, не знає), то кількість дій буде значно менше, ніж в разі перемішаних вхідних даних.
Як правило, складність алгоритмів підраховують окремо за кількістю порівнянь і за кількістю переміщень даних в пам'яті (пересилань), оскільки виконання цих операцій займає різний час. Однак точні значення вдається знайти рідко, тому для оцінки алгоритмів обмежуються лише поняттям "пропорційно", яке не враховує конкретні значення констант, що входять в підсумкову формулу. Загальну ж ефективність алгоритму зазвичай оцінюють "в середньому": як середнє арифметичне від складності алгоритму "в кращому випадку" і "в гіршому випадку", тобто (Eff_best + Eff_worst) / 2.
Сортування простими вставками
Найпростіший спосіб сортування 2 В назвах алгоритмів ми будемо слідувати Батога. який приходить в голову, - це впорядкування даних у міру їх надходження. В цьому випадку при введенні кожного нового значення можна спиратися на той факт, що всі попередні елементи вже утворюють відсортовану послідовність.
- Перший елемент записати "не роздумуючи".
- Поки не закінчиться послідовність даних, що вводяться, для кожного нового її елемента виконувати наступні дії:
- почавши з кінця уже існуючої впорядкованої послідовності, всі її елементи, які більше, ніж знову вводиться елемент, зрушити на 1 крок назад;
- записати новий елемент на місце, що звільнилося.
При цьому, зрозуміло, можна прочитати всі вводяться елементи одночасно, записати їх в масив, а потім "уявляти", що кожен черговий елемент був введений тільки що. На суть і структуру алгоритму це не вплине.
Реалізація алгоритму ПрВст