Алгоритми сортування як вони є
Сортування є розстановку об`єктів в певному порядку, наприклад, по спадаючій або по зростанню. Взагалі упорядкування елементів - найпоширеніша маніпуляція з даними, що полегшує надалі пошук потрібної інформації. Це багато в чому відноситься до різних системам управління базами даних. Алгоритми сортування в даний момент часу існують у великій кількості, хоча мають подібні риси (етапи): порівняння і перестановку елементів попарно до тих пір, поки послідовність не стане впорядкованим.
Алгоритми сортування можна класифікувати на внутрішні і зовнішні. Перші характеризуються тим, що всі сортовані елементи розміщуються в оперативній пам`яті і можливо отримати довільний доступ до будь-якого з них. Другі можуть працювати з даними, розміщеними в зовнішньої пам`яті (В файлах). Доступ до таких елементів може бути реалізований послідовно.
Зручніше сортувати елементи, коли вони знаходяться в структурі одновимірного масиву. У кожного такого елемента є порядковий номер, і звернення до елементу масиву відбувається за індексом. Алгоритми сортування в цьому випадку виходять найбільш простими і зрозумілими для використання.
Розглянемо внутрішній алгоритм сортування по спадаючій методом бульбашки і його вдосконалену версію, що відрізняється витрачається часом на сортування. Сортування методом бульбашки насправді має безліч назв. Його називають також методом лінійної сортування або методом обмінного сортування вибором. Але, втім, справа не в назві. Чому бульбашка? Опинившись у воді, пухирець повітря спливе, так як він легше. Так, наприклад, при сортуванні по зростанню нагорі виявиться найменший з елементів.
Розглянемо перший варіант алгоритму сортування масиву методом бульбашки. Словесний алгоритм сортування масиву, що має ідентифікатор mas і складається з N елементів, виглядає наступним чином:
1. Помістити на місце першого елемента (mas [1]) найбільший елемент масиву. Для цього будемо порівнювати його по черзі з усіма залишилися елементами (mas [2], mas [3] ... mas [N]). Якщо виявиться, що будь-якої з решти елементів більше mas [1], то потрібно поміняти їх місцями (через додаткову змінну buf).
2. Виключивши з розгляду елемент mas [1], повторити пункт 1 для елемента mas [2].
3. Ці дії повторювати для всіх елементо, крім останнього.
Реалізація алгоритму сортування бульбашкою на мові програмування Паскаль:
Про другий варіант (вдосконалений метод бульбашки) можна сказати, що це алгоритм швидкого сортування. Так, якщо спробувати його використовувати для сортування вже відсортованого масиву, алгоритм закінчить свою роботу вже після першого проходу по елементах масиву. А значить, що не витрачатимемо обчислювальні ресурси системи і час на безглузде порівняння елементів.
Наведемо реалізацію цього алгоритму сортування для мови програмування Паскаль:
Отже, алгоритми сортування є засобом упорядкування послідовностей даних. При виборі певного алгоритму слід враховувати витрати з точки зору часу і ресурсів системи.
