Алгоритми сортування як вони є

Алгоритми сортування як вони є

Сортування представляє собою розстановку об 'єктів у певному порядку, наприклад, по збиттю або за зростанням. Взагалі впорядкування елементів - найпоширеніша маніпуляція з даними, що полегшує в подальшому пошук потрібної інформації. Це багато в чому стосується різних систем керування базами даних. Алгоритми сортування зараз часу існують у великій кількості, хоча мають подібні риси (етапи): порівняння і перестановку елементів попарно до тих пір, поки послідовність не стане впорядкованою.


Алгоритми сортування можна класифікувати на внутрішні та зовнішні. Перші характеризуються тим, що всі сортовані елементи розміщуються в оперативній пам 'яті і можливо отримати довільний доступ до будь-якого з них. Інші можуть працювати з даними, розміщеними у зовнішній пам 'яті (у файлах). Доступ до таких елементів можна реалізувати послідовно.


Зручніше сортувати елементи, коли вони знаходяться в структурі одномірного масиву. У кожного такого елемента є порядковий номер, і звернення до елемента масиву відбувається за індексом. Алгоритми сортування в цьому випадку виходять найбільш простими і зрозумілими для використання.

Розгляньмо внутрішній алгоритм сортування зі збування методом бульбашки і його вдосконалену версію, що відрізняється витраченим часом на сортування. Сортування методом бульбашки насправді має безліч назв. Його називають також методом лінійного сортування або методом обмінного сортування вибором. Але, втім, справа не в назві. Чому бульбашка? Опинившись у воді, бульбашка повітря спливе, оскільки вона легша. Так, наприклад, при сортуванні за зростанням нагорі виявиться найменший з елементів.

Розгляньмо перший варіант сортування масиву методом бульбашки. Словесний алгоритм сортування масиву, що має ідентифікатор mas і складається з N елементів, виглядає наступним чином:

1. Розташувати на місці першого елемента (mas [1]) найбільший елемент масиву. Для цього будемо порівнювати його по черзі з усіма елементами, що залишилися (mas [2], mas [3]... mas[N]). Якщо виявиться, що якийсь з решти елементів більше mas [1], потрібно поміняти їх місцями (через додаткову змінну buf).

2. Виключивши з розгляду елемент mas [1], повторити пункт 1 для елемента mas [2].

3. Ці дії повторювати для всіх елементо, крім останнього.


Реалізація алгоритму сортування бульбашкою мовою програмування Паскаль:

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

Наведемо реалізацію цього алгоритму сортування для мови програмування Паскаль:

Отже, алгоритми сортування є засобом впорядкування послідовностей даних. При виборі певного алгоритму слід враховувати витрати з точки зору часу і ресурсів системи.