На практиці частіше застосовуються поліпшені методи сортування, так як прямі методи мають відносно низьку швидкодію.
Однак, при невеликій довжині масиву і / або особливому вихідному розташуванні елементів, прямі методи також дають хороший результат.
Розглянемо принципи основних (прямих) методів сортування.
Сортування обміном (метод «бульбашки»)
Послідовно порівнюються пари сусідніх елементів x [k] і x [k +1] (k = 1,2. N -1) і, якщо їх взаємне розташування не задовольняє заданій умові, то вони переставляються (міняються місцями).
Відшукується максимальний (мінімальний) елемент і переноситься в кінець масиву. Потім цей метод застосовується до всіх елементів, крім останнього (він вже знаходиться на своєму місці) і т.д.
Інший варіант методу - перенесення знайденого елемента в початок масиву і подальше застосування методу до всіх елементів, крім першого і т.д.
Масив розділяється на дві частини: відсортовану і невідсортовану. Елементи з невідсортоване частини по черзі вибираються і вставляються в відсортовану частину таким чином, що не порушують упорядкованість елементів. На початку в якості відсортованої частини приймають тільки один перший елемент.
За кількістю порівнянь всі методи мають квадратичну залежність від довжини масиву
За кількістю присвоювання:
· Методи обміну і вставки мають квадратичну залежність від довжини масиву
· Метод вибору має число присвоювання порядку n * ln (n)
Фахівці радять використовувати метод вибору для сортування складних структур даних, у випадках, коли на одне порівняння виконується велика кількість присвоювання.
В середньому методи вставки та вибору виявляються приблизно еквівалентними і в кілька разів (в залежності від довжини масиву) краще, ніж метод обміну.
До поліпшених методів сортування відносяться, наприклад, такі алгоритми:
ü сортування за допомогою включень з зменшуються відстанями;
ü сортування за допомогою дерева;
ü сортування за допомогою поділу (швидке сортування Хоара)
рекурсивних АЛГОРИТМИ
Зустрічаються такі випадки, коли завдання розбивається на підзадачі, які в свою чергу мають ту ж структуру, що і основне завдання.
У таких випадках використовують механізм, який називається рекурсією.
Спосіб виклику підпрограми, в якому підпрограма викликає сама себе, називають рекурсією.
Підпрограми, що реалізують рекурсію, називаються рекурсивними підпрограмами.
Пояснимо механізм рекурсивних підпрограм за допомогою класичного прикладу використання рекурсії.
Обчислення факторіала числа.
Обгрунтування вибору способу реалізації.
Звернемо увагу на те, що обчислити факторіал числа N можна наступним чином:
Реалізуємо такий алгоритм з використанням механізму рекурсії.
Так як підпрограма буде виробляти обчислення значення, то реалізовувати її будемо в вигляді функції.
function Fact (n: byte). integer;
if n = 0 then Fact: = 1
else Fact: = n * Fact (n-1);
Описаний вище механізм часто називають прямою рекурсії.
Існує ще один рекурсивний механізм - непряма рекурсія.
Механізм застосовується для реалізації наступної ситуації.
Перша підпрограма викликає другу, ще не описану.
Продемонструємо ситуацію на прикладі.
procedure A (var x: real);