Більш важливим для вибору алгоритму є місце розташування даних - в оперативній пам'яті комп'ютера або на зовнішньому пристрої.
Тут відіграє роль розходження в основних критеріях якості - для даних в оперативній пам'яті основними позитивними властивостями методу є швидкодія і потреби в додатковій пам'яті. Для дискових файлів дуже важливим показником є кількість звертань до пристрою для виконання операцій уведення-висновку - воно повиннео бути мінімальним.
Традиційно розрізняють внутрішнє сортування, у якій передбачається, що дані знаходяться в оперативній пам'яті, і важливо оптимизировать число дій програми (для методів, заснованих на порівнянні, число порівнянь, обмінів елементів і ін.), і зовнішню, у якій дані зберігаються на зовнішньому пристрої з повільним доступом (магнітні стрічка, барабан, диск, флешка) і насамперед треба знизити число звертань до цьому пристрою.
У цій роботі розглянемо алгоритми внутрішнього сортування масивів елементів, тому що вони більш важливі більшості програмістів у повсякденній практиці.
Варто помітити, що алгоритм сортування злиттям зручно застосовувати і при сортуванні зовнішніх даних. При цьому мова буде йти про злиття файлів.
Сформулюємо постановку задачі сортування даних для внутрішнього сортування одномірного числового масиву по зростанню.
Мається одномірний масив чисел, що складає з n елементів: X[n]. Переставити елементи масиву так, щоб їхні значення розташовувалися в порядку зростання. Іншими словами, для будь-якої пари елементів X[і] і X[і+1] виконується нерівність виду:
X[і] <= X[і+1].
У цій задачі однозначно визначається структура даних для внутрішнього сортування (одномірний масив) і порядок упорядкування елементів. Ключем для визначення порядку елементів є саме числове значення елемента масиву. Результатом рішення задачі повинна бути програма сортування масиву одним або декількома методами.
При розробці програми можна скористатися різними алгоритмами. Найбільш відомими є наступні:
- метод сортування обмінами ("бульбашкове" сортування);
- метод сортування включенням;
- метод сортування вибором елемента;
- метод поділу (алгоритм "швидкої" сортування метод Хоара);
- метод Шелла;
- метод злиття.
1.5 Сортування бульбашковим методом
Найбільш відомим (і найбільше "безславним") є сортування бульбашковим методом. Його популярність пояснюється назвою, що запам'ятовується, і простотою алгоритму. Однак, це сортування є одним із самих гірших серед усіх коли-небудь, придуманих сортувань.
Сортування бульбашковим методом використовує метод обмінного сортування. Вон заснован на виконанні в циклі операцій порівняння і при необхідності обміну сусідніх елементів. Його назва відбувається через подобу процесові руху бульбашок у резервуарі з водою, коли кожна бульбашка знаходить свій власний рівень. Нижче показана найпростіша форма програми сортування бульбашковим методом:
{ сортування бульбашковим методом}
procedure Bubble(var item: DataArray; count:integer);
var
i,j : integer;
x : DataItem;
begin
for i := 2 to count do
begin
for j := count downto i do
if item[j-1]>item[j] then
begin
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
end;
end;
end; {кінець сортування бульбашковим методом}
У цьому випадку дане "item" є масивом елементів "DataItem", що сортується, а дане "count" містить число елементів у масиві.
Сортування бульбашковим методом мають два цикли. Оскільки число елементів масиву задається перемінної "count", зовнішній цикл викликає перегляд масиву count - 1 раз. Це забезпечує перебування кожного елемента у своєї позицій після завершення процедури. Внутрішній цикл призначений для фактичного виконання операцій порівняння й обміну.
Для ілюстрації роботи сортування бульбашковим методом нижче подані результати кожного етапу сортування масиву "dcab":
вихідне положення: d c a b;
перший прохід: a d c b;
другий прохід: a b d c;
третій прохід: a b c d.
При аналізі всякого сортування визначається число операцій порівняння й обміну, виконаних у кращому, середньому і гіршому випадках. Для сортування бульбашковим методом число порівнянь залишається незмінним, оскільки два цикли завжди виконуються задане число раз поза залежністю від упорядкованості вихідного масиву. Це означає, що при сортуванні бульбашковим методом завжди виконується 1/2 (n2-n) операцій порівняння, де "n" задає число сортируемых елементів масиву. Ця формула виводиться на тій підставі, що зовнішній цикл сортування бульбашковим методом виконується n-1 раз, а внутрішній цикл виконується n/2 разів. Їхнє перемножування дасть зазначену формулу. Число операцій обміну буде нульовим для найкращого випадку, коли вихідний масив уже є відсортованим. Число операцій обміну для середнього випадку буде дорівнює 3/4 (n2-n), а для найгіршого випадку буде дорівнює 3/2 (n2-n) раз. Можна помітити, що в міру погіршення упорядкованості вихідного масиву число неупорядкованих елементів наближається до числа порівнянь (кожен неупорядкований елемент вимагає три операції обміну). Сортування бульбашковим методом називають квадратичним алгоритмом, оскільки час його виконання пропорційно квадратові числа сортуємих елементів. Сортування великого числа елементів бульбашковим методом вимогає дуже багато часу, тому що час виконання сортування знаходиться в квадратичній залежності від числа елементів масиву. Наприклад, якщо не враховувати час операцій обміну, виконуваних для перестановки неупорядкованих елементів, то тоді при виконанні однієї операції порівняння протягом 0,001 секунд сортування десяти елементів займе 0,05 секунд, сортування ста елементів займе 5 секунд, а сортування 1000 елементів займе 500 секунд. Сортування 100 000 елементів (такий розмір має невеликий телефонний довідник) вимогала б 5 000 000 секунд або близько 1400 годин (тобто два місяці безперервної роботи)! Сортування бульбашковим методом можна до деякої міри поліпшити і тим самим небагато поліпшити її тимчасові характеристики. Можна, наприклад, помітити, що сортування бульбашковим методом володіє одною особливістю: розташований не на своєму місці (наприкінці) масиву елемент (наприклад, елемент "а" у масиві "dcab") досягає свого місця за один прохід, а елемент, розташований на початку масиву (наприклад, елемент "d"), дуже повільно досягає свого місця. Необов'язково всі перегляди робити в одному напрямку. Замість цього всякий наступний перегляд можна робити в протилежному напрямку. В цьому випадку сильно віддалені від свого місця елементи швидко переміщатимуться у відповідне місце. Нижче показана поліпшена версія сортування бульбашковим методом, що одержав назву "човникового сортування" через відповідний характер рухів по масиву.
Хоча це сортування є поліпшенням бульбашковим методом, його не можна рекомендувати для використання, оскільки час виконання як і раніше залежить квадратично від числа елементів. Число порівнянь не змінюється, а число обмінів зменшується лише на незначну величину.
{човникове сортування є поліпшеною версією сортування бульбашковим методом}
procedure Shaker(var item: DataArray; count:integer);
var
j, k, l, r: integer;
x: DataItem;
begin
l := 2; r := count; k := count;
repeat
for j := r downto l do
if item[j-1] then
begin { обмін }
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
k := j;
end;
l := k+1;
for j := l to r do
if item[j-1]>item[j] then
begin { обмін }
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
k := j;
end;
r := k-1;
until l>r
end; {кінець човникового сортування}
1.6 Сортування вибором елемента
При сортуванні вибором вибирається елемент із найменшим значенням і робиться його обмін з першим елементом масиву. Потім знаходиться елемент із найменшим значенням із що залишилися n-1 елементів і робиться його обмін із другим елементом і т.д. до обміну двох останніх елементів. Наприклад, якщо сортування вибором застосувати для масиву "bdac", те будуть отримані наступні проходи:
вихідне положення: b d a c;
перший прохід: a d b c;
другий прохід: a b b c;
третій прохід: a b c d.
На жаль як і в сортуванні бульбашковим методом зовнішній цикл виконується n-1 раз, а внутрішній цикл виконується n/2 разів. Це значить, що число порівнянь для сортування вибором дорівнює 1/2 (n2-n) і це сортування буде виконуватися занадто повільно для великого числа елементів. Число операцій обміну в найкращому випадку дорівнює 3(n-1), а в гіршому випадку дорівнює n2/4+3(n-1). У кращому випадку (коли вихідний масив вже упорядкований) буде потрібно поміняти місцями тільки n-1 елементів, а кожна операція обміну вимагає три операції пересилання.
{сортування вибором}
procedure Selekt(var item: DataArray; count:integer);
var
i, j, k: integer;
x: DataItem;
begin
for i := i to count-1 do
begin
k := i;
x := item[i];
for j := і+1 to count do {знайти елемент із найменшим значенням}
if item[j]<x then
begin
k := j;
x := item[j];
end;
item[k] := item[і]; {обмін}
item[і] := x;
end;
end; {кінець сортування вибором}
У середньому число операцій обміну дорівнює n(ln+y), де "y" є константою Эйлера, приблизно рівної 0,577216. Це значить, що незважаючи на однакове число операцій порівнянь для сортувань бульбашковим методом і сортувань вибором, число операцій обміну для середнього випадку буде значно меншим для сортування вибором.
1.7 Сортування включенням
Сортування включенням є останньою з класу простих алгоритмів сортування. При сортуванні включенням спочатку упорядковуються два елементи масиву. Потім робиться включення третього елемента у відповідне місце стосовно перших двох елементів.
Цей процес повторюється доти, поки всі елементи не будуть упорядковані. Наприклад, для масиву "dcab" сортування включенням буде проходити в такий спосіб: