глава 18

Загальні відомості

Одне зі значень слова сортування - впорядкування списку чогось по зростанню (краще сказати - по неубиванія, якщо в списку містяться рівні елементи).

Сортування - дуже важливе завдання в інформатиці. Дані, представлені у вигляді впорядкованого списку, наочніше. І, що ще важливіше, пошук в упорядкованих списках простіше: наприклад, знайти прізвище учня в класному журналі легше, якщо прізвища розташовані в алфавітному порядку.

Неубиванія можна розуміти в різних сенсах. Список держав можна впорядкувати за алфавітом, можна за кількістю населення, по площі, займаної державою, по щільності населення (стосовно населення до площі), за назвами столиць, по широкій або довготам столиць, по протяжності морської частини кордону, річного ВВП ... Та хіба мало величин, по неубиванія яких можна розташувати країни!

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

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

Більш екзотичний приклад упорядкування рядків можна зустріти в граматичних словнику української мови академіка А. А. Залізняка [18]. У цьому словнику для слів української мови наводяться у вигляді умовних позначень морфологічні описи: частина мови, схема (парадигма) зміни слів - парадигма відмінювання для імен, парадигма відмінювання дієслів та інші морфологічні особливості слів. Цікавий порядок слів у словнику Залізняка: перш йдуть слова, що закінчуються на а. потім - на б. і так далі. При співпадаючих буквах порівнюються попередні ім. Ясно, що використовується лексикографічний порядок, але не самих слів, а слів, в яких букви розташовані в зворотній послідовності. Такий порядок називається інверсним. Навіщо такий порядок прийнятий в словнику Залізняка? Справа в тому, що в українській мові інформація про граматичних властивостях слова як правило міститься в кінці слова, там, де закінчення і суфікси. Тому слова, подібні в граматичному сенсі, звичайно розташовуються поруч. Наприклад, слова, що закінчуються на ться. майже напевно є поворотними дієсловами.

Так чи інакше при упорядкуванні списків потрібно вміти порівнювати пари елементів, тобто встановлювати, чи менше перший елемент другого, більше, або елементи рівні. Хоча сенс слів «більше», «менше», «рівні» може бути різним, важливо, щоб при порівнянні елементів реалізовувалася тільки одна з цих трьох можливостей. Крім того, звичайно, передбачається, що поняття «більше» і «менше» взаємно-зворотні, тобто висловлювання «a менше b» рівносильно висловом «b більше a». Без цієї умови порядок в списку може бути недосяжний.