Теоретичні відомості

ЛАБОРАТОРНА РОБОТА № 5

СОРТУВАННЯ МАСИВІВ ІНФОРМАЦІЇ

Мета роботи: набути навички програмування алгоритмів, що реалізують зміну послідовності розташування елементів масиву по заданому закону.

Теоретичні відомості

Розглянемо масив цілих або дійсних чисел . Нехай потрібно переставити елементи цього масиву так, щоб після перестановки вони були упорядковані по убуванню: ≤ ≤ …≤ . Ця задача називається задачею сортування або упорядкування масиву. Таку ж задачу можна розглядати стосовно до упорядкування по незростанню: ≥ ≥…≥ . Якщо числа попарно різні, то можна говорити про убування і про зростання. Для розв'язання цієї задачі можна скористатися, наприклад, такими алгоритмами.

а) знайти елемент масиву, що має найменше значення, переставити його з першим елементом, потім проробити теж саме, почавши з другого елемента і т.д. Цей вид упорядкування називається сортуванням вибором;

б) послідовним переглядом чисел знайти найменше і таке, що a_i> . Поміняти місцями і , потім відновити перегляд, починаючи з елемента і т.д. Тим самим найбільше число пересунеться на останнє місце. Наступні перегляди необхідно починати знову спочатку, зменшуючи на одиницю кількість елементів, що переглядаються. Масив буде упорядкований після перегляду, у якому брали участь тільки перший і другий елементи. У такий спосіб реалізується сортування обмінами;

в) послідовним аналізом елементів a₁, вставити кожний новий елемент на відповідне місце в уже упорядковану сукупність a₁, . Це місце визначається послідовним порівнянням елемента з упорядкованими елементами a₁, . Такий вид сортування називається сортуванням простими вставками.