ів. Наприклад, якщо сортування вибором застосувати для масиву "bdac", то будуть отримані наступні проходи:
вихідне положення: bdac;
перший прохід: adbc;
другий прохід: abbc;
третій прохід: abc d.
На жаль як і в сортуванні бульбашковим методом зовнішній цикл виконується n-1 раз, а внутрішній цикл виконується n/2 разів. Це означає, що число порівнянь для сортування вибором одно 1/2 (n2-n) і ця сортування буде виконуватися занадто повільно для великого числа елементів. Число операцій обміну в найкращому разі дорівнює 3 (n-1), а в гіршому випадку дорівнює n2/4 +3 (n-1). У кращому випадку (коли вихідний масив вже впорядкований) буде потрібно поміняти місцями тільки n-1елементов, а кожна операція обміну вимагає три операції пересилки. br/>
{сортування вибором} Selekt (var item: DataArray; count: integer);, j, k: integer;: DataItem; i: = i to count-1 do: = i;: = item [i];
for j: = i +1 to count do {знайти елемент з найменшим значенням}
if item [j]
item [i]: = x;;; {кінець сортування вибором}
У середньому число операцій обміну одно n (ln + y), де "y" є константою Ейлера, приблизно рівної 0,577216. Це означає, що незважаючи на однакове число операцій порівнянь для сортувань бульбашковим методом і сортувань вибором, число операцій обміну для середнього випадку буде значно меншим для сортування вибором. br/>
2.6 Сортування вставкою
Сортування вставкою є останньою з класу простих алгоритмів сортування. Під час сортування вставкою спочатку впорядковуються два елементи масиву. Потім робиться вставка третього елемента у відповідне місце по відношенню до перших двом елементам. p align="justify"> Цей процес повторюється до тих пір, поки всі елементи не будуть впорядковані. Наприклад, для масиву "dcab" сортування вставкою проходитиме наступним чином:
вихідне положення: dcab;
перший прохід: cdab;
другий прохід: acdb;
третій прохід: abc d.
Нижче наводиться алгоритм сортування вставкою:
{сортування вставкою} Inser (var item: DataArray; count: integer);, l: integer;: DataItem; i: = 2 to count do: = item [i];: = i- 1; (x 0) do [j +1]: = item [j];: = j-1;; [j +1]: = x;
end;; {кінець сортування вставкою}
На відміну від сортування бульбашковим методом і сортування вибором число операцій порівняння для сортування вставкою залежить від вихідної упорядкованості масиву елементів. Якщо вихідний масив вже впорядкований, то число операцій порівняння одно n-1. p align="justify"...
