5.3. Сортування

Для самого загального випадку задача сортування може формулюватися так: мається деяка неупорядкована вхідна множина ключів, необхідно одержати вихідну множину тих же ключів, упорядкованих за зростанням або зменшенням в чисельному чи лексикографічному порядку. З усіх задач програмування, сортування, можливо, має найбільш широкий вибір алгоритмів рішення. У даному розділі будуть розглянуті внутрішні алгоритми сортувань на прикладі масивів; зовнішні сортування (сортування файлів) поки не розглядаються.

Фактори, що впливають на вибір алгоритму сортування:

а) порядок алгоритму: степеневий O(N^a), лінійні O(N) або логарифмічний O(log_a(N));

б) необхідний ресурс пам'яті. Чи повинні вхідна і вихідна множини розташовуватися в різних областях пам'яті чи вихідна множина може бути сформована на місці вхідної. У такому випадку наявна область пам'яті в ході сортування динамічно перерозподіляється між вхідною і вихідною множинами; в) вихідна упорядкованість вхідної множини. У вхідному наборі можуть бути присутні упорядковані ділянки. У крайньому випадку вхідна множина може виявитися вже упорядкованою. Одні алгоритми не враховують початкової упорядкованості і вимагають того самого часу для сортування (у тому числі і вже упорядкованої) множини даного обсягу, інші виконуються тим швидше, чим краще упорядкованість на вході;

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

д) складність алгоритму є не останнім показником при його виборі. Простий алгоритм вимагає меншого часу для його реалізації й імовірність помилки в реалізації його менше. При промисловому виготовленні програмного продукту вимоги дотримання термінів розробки і надійності продукту можуть навіть превалювати над вимогами ефективності функціонування.

Класифікація алгоритмів сортування за логічними характеристика-ми. Відповідно до цього підходу виділяють чотири групи алгоритмів сортування.

1) Сортування вибіркою. З вхідної множини вибирається наступний за критерієм упорядкованості елемент і включається у вихідну множину на наступне за номером місце.

2) Сортування включенням. З вхідної множини вибирається наступний за номером елемент і включається у вихідну множину на те місце, яке він повинен займати відповідно до критерію упорядкованості ключів.

3) Сортування розподілом. Вхідна множина розбивається на ряд підмножин (можливо, меншого обсягу) і сортування проводиться усередині кожної такої підмножини.

4) Сортування злиттям. Вихідна множина получається шляхом злиття маленьких упорядкованих підмножин.

Всі алгоритми сортувань розглянуті для прикладі упорядкування за зростанням ключів і наведені мовою Pascal. Тип SEQ визначений як:

type SEQ=array[1..n] of іnteger;