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