2.1 Сортування списків на пролозі

Сортування методом простої вставки

Нехай є список: [15, 11, 13, 12]. Треба відсортувати список в порядку зростання.

Алгоритм

Вибирається останній елемент старого списку і приєднується до нового списку. Вибирається другий елемент старого списку з кінця. Для нього шукається місце у новому списку за ознакою “елемент менше інших елементів списку”. Далі процес повторюється для 3, 4 елементів списку з кінця, поки новий список не стане впорядкованим.

Списки будуються за схемою:

Старий список Новий список

[15, 11, 13, 12] [ ]

[15, 11, 13] Вставили 12 [12]

[15, 11] Вставили 13 [12, 13]

[15] Вставили 11 [11, 12, 13]

[] Вставили 15 [11, 12, 13, 15]

Розглянемо програму, що реалізує метод простої вставки.

Domains

Lst=integer*

Predicates

Vk(lst, lst)

Vk2(integer, lst, lst)

Clauses

vk([],[]).

vk([X|L],M):-vk(L,N),vk2(X,N,M).

vk2(X,[A|L],[A|M]):-A<X,!,vk2(X,L,M).

vk2(X,L,[X|L]).

Goal

vk ([15, 11, 13, 12], M), write (M).

Робота процедур vk і vk2:

Процедура написана низхідним методом. Вона відокремлюємо по порядку голови старого списку L і заносить їх у стек. Порядок елементів списку в стеку зворотний. Процес повторюється доти, доки старий список не стане порожнім. Після досягнення граничної умови новий список N стає теж порожнім. Викликається процедура vk2.

Процедура “vk2” шукає місце верхнього елементу стеку в новому списку N. Якщо новий список порожній, то елемент вставляється в список.

Для не порожнього нового списку процедура порівнює фіксований елемент з поточним елементом нового списку. Якщо місце не підходить, то обирається наступний елемент списку. Інакше процедура добавляє елемент до нового списку в знайденому місці.

Процедура повторюється до тих пір, поки зі стеку не виберуться всі елементи. Процедура написана висхідним методом.

Сортування методом пухирця

Нехай є список: [13, 11, 12, 15]. Треба відсортувати список в порядку спадання.

Алгоритм

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

Списки будуються за схемою:

[13, 11, 12, 15]

15 11 11 11

12 15 12 12

11 12 15 13

13 13 13 15

domains

lst=integer*

Predicates

P(lst,lst)

Pr(lst,lst,lst)

Clauses

P(L,S):-pr(X,[A,B|Y],L), A<B, pr(X,[B,A|Y],M ),p(M,S).

p(L,L).

pr([],L,L).

pr([H|L1],L2,[H|L3]):-pr(L1,L2,L3).

Goal

p([15,11,13,12],S),write(S).

Робота процедури P

Процедура Р розбиває список L на різні варіанти підсписків за допомогою першого виклику процедури pr. Це дозволяє двигатися по списку далі, обирати наступні елементи для порівняння. Одночасно другий аргумент процедури pr відокремлює від другого підсписку перші два аргументи А и В для порівняння.

Порівнюються значення елементів А і В. Якщо нерівність невірна, то відбувається повернення на pr, і вона розбиває список на наступні підсписки.

Якщо нерівність вірна, це значить, що елементи стоять не в тому порядку. Друге використання процедури pr приєднує до підсписку Х підсписок, з елементами в іншому порядку. Результат розміщується в М. Процес повторюється доти, доки скрізь А<B буде невірним. Тобто наша відсортованість вірна і результат зберігається. Процедура написана висхідним методом.