Задача сортування.
- Сортування вибором.
- Сортування вставками
- Сортування обміном.
(включенням).
Сортування масивів
У прикладних програмах широко поширені два типи операцій, зв'язаних з масивами:
- Упорядкування елементів масиву за зростанням чи спаданням (сортування);
2) Пошук елемента в масиві.
Ми сьогодні розглядаємо одну з найбільш важливих задач для програмування - задача сортування.
Під сортуванням звичайно розуміють перестановки елементів будь-якої послідовності у визначеному порядку.
Сортування масиву — це зміна порядку розташування його елементів за певним критерієм.
Тобто, сортування - це впорядкування елементів за якоюсь ознакою.
Методи сортування
Відомо багато методів сортування масиву, що відрізняються швидкодією й обсягом оперативної пам'яті, яка при цьому використовується. Серед цих методів можна вирізнити методи внутрішнього та зовнішнього сортування. Методи внутрішнього сортування не передбачають використання допоміжних масивів. Ці методи застосовують до масивів, що повністю розташовані в оперативній пам'яті. Методи зовнішнього сортування застосовують до великих масивів даних, які зберігаються на зовнішніх носіях.Сьогодні ми розглянемо методи внутрішнього сортування масиву, обмежуючись задачею сортування за зростанням.
Методи внутрішнього сортування прийнято поділяти на дві групи: елементарні (прямі) та удосконалені методи.
Найбільш відомими елементарними методами сортування масиву є:
- сортування вставкою (включенням);
- сортування вибором;
- сортування обміном (бульбашкове сортування).
- швидке сортування, або метод Хоара;
- сортування включенням зі спадним приростом, або метод Шелла;
- сортування за допомогою дерева, або пірамідальне сортування;
- сортування методом злиття.
З удосконалених методів сортування найчастіше використовуються такі:
Оцінка алгоритмів сортування
- Час сортування - основний параметр, що характеризує швидкодію алгоритму.
- Пам'ять - один з параметрів, який характеризується тим, що ряд алгоритмів сортування вимагають виділення додаткової пам'яті під тимчасове зберігання даних.
- Стійкість - це параметр, який відповідає за те, що сортування не міняє взаємного розташування рівних елементів.
Задачі сортування
Подана послідовність a довжини n даних типу Data. На типі Data визначене відношення порядку, тобто операції < , > , ≤ , ≥ . Необхідно відсортувати послідовність, тобто переставити її елементи, таким чином, що для кожного ai виконуватиметься співвідношення ai * ai+1, де i = 1, 2, ... n – 1, а * є однією із зазначених операцій (< для сортування за зростанням, <= — за неспаданням і т. д.).
Сортування вибором
Алгоритм працює таким чином:
- Знаходить у списку найменше значення
- Міняє його місцями із першим значеннями у списку
- Повторює два попередніх кроки, доки список не завершиться (починаючи з другої позиції)
Фактично, таким чином ми поділили список на дві частини: перша (ліва) — повністю відсортована, а друга (права) — ні.
Ось приклад сортування масиву з п'яти елементів за даним алгоритмом: 64 25 12 22 11
64 25 12 22 11
11 25 12 22 64
11 12 25 22 64
11 12 22 25 64
Сортування вибором
Сортування вставками
Ідея методу:
Послідовність ділиться на дві частини — відсортовану (спочатку її довжина дорівнює 0) і невідсортовану (довжини n).
На кожному кроці алгоритму вибирається один з елементів невідсортованої послідовності і шукається його порядкове місце серед елементів відсортованої (при цьому варто використовувати бінарний чи інтерполяційний пошук). При знаходженні порядкового місця частина елементів послідовності «зсувається», вивільняючи місце для розміщення елементів.Сортування обміном (метод бульбашки)
Ідея методу. У послідовності порівнюються два сусідні елементи. Якщо один з елементів, не відповідає критерію сортування, ці два елементи обмінюються місцями. Прохід по послідовності продовжується доки дані не будуть відсортованими.
Таким чином, елементи з меншим значенням просуваються до початку масиву (спливають), а елементи з більшим значенням - до кінця масиву (тонуть). Цей процес повторюється на одиницю менше разів, ніж елементів в масиві.
Сортування обміном
Приклад реалізації крок за кроком
Візьмемо масив чисел «5 1 4 2 8», і за допомогою даного алгоритму, відсортуємо його від найменшого до найбільшого елементу. На кожному кроці, елементи, виділені жирним шрифтом будуть порівнюватись. Перший прохід: (5 1 4 2 8) (1 5 4 2 8) Тут, алгоритм порівнює перші два елементи, і міняє їх місцями. (1 5 4 2 8) (1 4 5 2 8) (1 4 5 2 8) (1 4 2 5 8) (1 4 2 5 8) (1 4 2 5 8) Тут порівнювані елементи знаходяться на своїх місцях, тож алгоритм не міняє їх місцями. Другий прохід: (1 4 2 5 8) (1 4 2 5 8) (1 4 2 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8)Тепер наш масив повністю відсортований, однак, алгоритм цього ще не знає. Йому
потрібен ще один «пустий» прохід, під час якого він не поміняє місцями жодного елементу.
Третій прохід: (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8)Нарешті, масив відсортовано, і алгоритм може припинити свою роботу.
Домашнє завдання:
- Вивчити § 2, п.2.1 з підручника І.Т. Зарецька, А.М. Гуржій, О.Ю.Соколов. «Інформатика 10-11кл.», ч.2
- самостійне вивчення теми: «Задача пошуку. Послідовний пошук. Бінарний пошук» §2, п.2.2 з підручника І.Т. Зарецька, А.М. Гуржій, О.Ю.Соколов. «Інформатика 10-11кл.», ч.2.