justify"> Сортування вставкою:
Розглянемо застосування методу зменшення на одиницю до сортування масиву А [0 .. n-1]. Дотримуючись ідеї методу, вважаємо, що завдання меншого розміру, а саме сортування масиву А [0 .. n-2], вже вирішена і є відсортований масив розміром n-1: А [0] ... А [n-2]. Яким чином скористатися цим рішенням завдання меншого розміру для отримання рішення вихідної задачі, яка враховує наявність елемента А [n-1]? Очевидно, все, що необхідно, - це знайти потрібну позицію серед відсортованих елементів і вставити туди елемент А [n - 1]. p> Для цього використовується наступний спосіб: сканується відсортований підмасив зліва направо, поки не досягається перший елемент, більший або дорівнює А [n-1], і після цього здійснюється вставка безпосередньо перед знайденим елементом.
Хоча сортування вставкою заснована на рекурсивному підході, більш ефективною буде її реалізація знизу вгору, тобто ітеративна. Елемент А [i] (починаючи з елемента А [1] і закінчуючи А [n-1]) вставляється у відповідне місце серед перших i елементів масиву (які до цього моменту вже відсортовані). Однак на відміну від сортування вибором елемент у загальному випадку вставляється не в остаточну позицію, яку він буде займати в повністю відсортованому масиві. p> Нижче наведено псевдокод даного алгоритму.
Алгоритм Insertions'ort (А [0 .. n-1])
// Сортування масиву методом сортування вставкою
// Вхідні дані: Масив А [0 .. n -1] з п упорядковуваних
// елементів
// Вихідні дані: Масив А [0 .. n - 1], відсортований
// в неубутною порядку
for i = 1 to n - 1 do
v = A [i] = i - 1j 0 and A [j]> v do [j + 1] = A [j]
j = j - 1
A [j + 1] = v
Робота алгоритму проілюстрована на рис. 2.3. br/>В
Рис. 2.3. Приклад сортування вставкою
Сортування підрахунком:
Ідея даного методу полягає в тому, щоб підрахувати для кожного елемента сортується загальна кількість елементів, менших даного, і занести отриманий результат в таблицю. Отримані числа вказують позиції елементів у відсортованому списку: наприклад, якщо для деякого елемента це кількість дорівнює 10, то він повинен бути одинадцятим (його індекс буде дорівнювати 10, якщо індекси починаються з 0) в відсортованому масиві. Таким чином, можна відсортувати список, просто копіюючи його елементи у відповідні позиції в новому, відсортованому списку. Такий алгоритм називається сортуванням підрахунком порівнянь (comparison counting) (рис. 2.4). br/>В
Рис. 2.4. Приклад сортування підрахунком порівнянь
Псевдокод даного алгоритму.
Алгоритм ComparisonCountingSort (А [0 .. n - 1])
// Сортування масиву підрахунком порівнянь
// Вхідні дані: Масив А [0 .. n - 1] упорядковуваних значень
// Вихідні дані: Масив S [0 .. n - 1] елементів А,
// відсортованих у неубутною порядку
for i = 0 to n - 1 do
Count [i] = 0i = 0 to n - 2 doj...
