Сортування одновимірного масиву

У розд. 3.1 була розглянута задача сортування всього трьох чисел. А якщо чисел багато (20, 100, 100000)?

Немає потреби пояснювати, що як при декларативному, так і при процедурному способі вирішенні цієї задачі виникнуть проблеми.

Про розв'язок однієї з них (збереження великої кількості різних чисел у масивах) йшла мова раніше.

Друга проблема полягає в тому що в розглянутих алгоритмах кількість порівнянь буде різко зростати зі збільшенням кількості порівнюваних чисел (згадайте відповіді на питання до попереднього розділу).

Вирішення другої проблеми — тема цього і наступних розділів даної глави.

По-перше, як і в інших алгоритмах, розглянутих в попередній главі, в алгоритмах сортування можна використовувати вже знайомі Вам цикли — повторювані не дуже складні комбінації порівнянь чисел. І від кількості чисел буде залежати не кількість порівнянь на одному кроці циклу, а тільки кількість цих кроків.

По-друге (і це головна тема даної глави), в алгоритмах сортування ми будемо застосовувати ідею рекурсії.

Спочатку вирішимо більш просту задачу, алгоритм якої ми дуже коротко описали на початку глави, — задачу рекурсивного пошуку максимального з N чисел.

Використовуючи цей алгоритм, визначимо рекурсивну функцію МаксЕлемент, що буде повертати максимальний елемент одномірного масиву Масив. Аргументів у цієї функції два: Масиви і n (сам масив і число його елементів).

Код 3.7

Дуже часто потрібно знаходити не значення максимального елемента, а його позицію — порядковий номер у масиві. Наступний код дуже нагадує код 3.7:

Код 3.8

А тепер перейдемо до сортування одномірного масиву. Сортуванням одномірного масиву називається така процедура, у результаті якої його елементи змінюють свої порядкові номери так, що кожен наступний у списку елемент не менший (У мові Visual Basic можна сортувати не тільки числа, але і рядки. При цьому вони вистроюються в лексикографічному порядку, як в енциклопедії. Один рядок вважається більшим за інший, якщо при їхньому перегляді зліва направо і відсіканні від них по одному символі виявляється, що код ASCII символу першого рядка більший за код ASCII символу другого рядка, або ж якщо другий рядок є лівим підрядком першого рядка. Наприклад: рядок «Петрівна» більший рядка «Петрович», а рядок «Петрович» більший рядка «Петров». (Не забудьте, що символ пробілу теж має код ASCII.)), ніж попередній.

Приклад 3.3. Початковий порядок елементів масиву M був таким:
M(0)=5, M(1)=15, M(2)=12, M(3)=2, M(4)=22, M(5)=5.

Після сортування порядок елементів масиву M став таким:
M(0)=2, M(l)=5, M(2)=5, M(3)=12, M(4)=15, M(5)=22.

Існує кілька алгоритмів сортування. Вони відрізняються один від одного складністю і швидкістю роботи. Якщо говорити більш точно, то не швидкістю, а ефективністю — залежністю часу роботи алгоритму від довжини сортованого масиву. Як правило, чим ефективніше працює алгоритм, тим він складніший. (За все треба платити!)

Розглянемо два з них (далеко не найгірші). Це алгоритми сортування вибором і сортування вставкою. Ще два алгоритми сортування (кулькового та наївного сортування) приведені в розд. 3.6.