Алгоритм
Сортування методом пухирця
Алгоритм
Вибирається останній елемент старого списку і приєднується до нового списку. Вибирається другий елемент старого списку з кінця. Для нього шукається місце у новому списку за ознакою “елемент менше інших елементів списку”. Далі процес повторюється для 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).
Процедура Р розбиває список L на різні варіанти підсписків за допомогою першого виклику процедури pr. Це дозволяє двигатися по списку далі, обирати наступні елементи для порівняння. Одночасно другий аргумент процедури pr відокремлює від другого підсписку перші два аргументи А и В для порівняння.
Порівнюються значення елементів А і В. Якщо нерівність невірна, то відбувається повернення на pr, і вона розбиває список на наступні підсписки.
Якщо нерівність вірна, це значить, що елементи стоять не в тому порядку. Друге використання процедури pr приєднує до підсписку Х підсписок, з елементами в іншому порядку. Результат розміщується в М. Процес повторюється доти, доки скрізь А<B буде невірним. Тобто наша відсортованість вірна і результат зберігається. Процедура написана висхідним методом.
7.8. Складені списки
Пролог дозволяє працювати тільки зі списками, які мають елементи одного типу. Для утворення списків, які мають елементи різних доменів використовують структури.
Наприклад, списoк, що має елементами рядки і цілі числа, об’являють так:
Domains
Strukt = f(string);
f (integer).
List = strukt*
А список такого типу може мати вигляд: [f(“К12”),f(“Р32”),f(14),f(18)]
8. ПРЕДИКАТИ ВВОДУ-ВИВІДУ
