2. С помощью процедуры div1 разбить список на два:
— меньший либо равный H (Small)
— больший H (Big)
3. Методом быстрой сортировки отсортировать списки Small и Big.
4. Соединить списки Small_sort и [H|Big_sort] с помощью процедуры conc.
Опишем предикат, производящий сортировку списка методом быстрой сортировки:
supersort(list,list)
Правила, реализующие этот способ сортировки, имеют следующую структуру:
supersort([],[]).
supersort([H|T],Sorted_list) :-
div1(H,T, Small,Big),
supersort(Small,Small_sort),
supersort(Big,Big_sort),
conc(Small_sort,[H|Big_sort],Sorted_list).
Процедуры conc и div1 уже были описаны ранее.
4. БЫСТРАЯ СОРТИРОВКА_1
Программа быстрой сортировки будет работать очень неэффективно, если один из списков Big и Small существенно длиннее другого. Это произойдет, например, в случае, когда список почти отсортирован. От этого недостатка можно избавиться следующим образом: разбивать список на два списка примерно одинаковой длины.
Итак, необходимо:
1. Разбить L на два списка L1 и L2 примерно одинаковой длины.
2. Отсортировать их, получив списки S1 и S2.
3. Слить отсортированные S1 и S2, получив отсортированный список S.
Рекурсивное правило сортировки supersort1 будет выглядеть так:
supersort1(L,S):-
% разделение на два равных списка
div2(L,L1,L2),
supersort1(L1,S1),
supersort1(L2,S2),
% соединение отсортированных списков
concsort (S1,S2,S).
Определим, что в этой сортировке будет являться граничным условием, то есть задачей, решаемой непосредственно. Список [X], состоящий из одного элемента, правило div2 разделит на два: пустой [] и одноэлементный [X].
Следовательно, у нашей сортировки будут два граничных условия:
supersort1([],[]).
supersort1([X],[X]).
Опишем процедуру div2.
Идея очень простая:
1. Первый элемент списка [X,Y|T] отправляется в список L1, второй — в список L2.
2. Вызывается div2 для хвоста T.
div2([],[],[]).
div2([X],[X],[]).
div2([X,Y|L],[X|L1],[Y|L2]):-
div2(L,L1,L2).
Остается описать процедуру concsort(S1,S2,S) слияния двух отсортированных списков S1 и S2 в отсортированный список S.
Идея следующая:
1. Сравниваются головы H1 и H2 исходных списков. Меньший из этих элементов становится головой целевого списка S.
2. Остатки исходных списков с помощью concsort соединяются в хвост целевого.
concsort([H1|T1],[H2|T2],[H1|T]):-
H1<=H2,!,
concsort(T1,[H2|T2],T).
concsort([H1|T1],[H2|T2],[H2|T]):-
concsort([H1|T1],T2,T).
Так как мы заранее не знаем, какой из списков L1, L2 кончится раньше, то необходимо иметь два граничных условия:
concsort([],L,L).
concsort(L,[],L).
/* Программа 7.3 «очень быстрая сортировка». */
domains
list=integer*
predicates
% очень быстрая сортировка
supersort1(list,list)
% разделение на два примерно равных списка
div2(list,list,list)
% соединение двух отсортированных списков
concsort(list,list,list)
goal
supersort1([1,7,95,1,9,3],L),write(L),nl.
clauses
supersort1([],[]).
supersort1([X],[X]).
supersort1(L,S):-
div2(L,L1,L2),
supersort1(L1,S1),
supersort1(L2,S2),
concsort(S1,S2,S).
div2([],[],[]).
div2([X],[X],[]).
div2([X,Y|L],[X|L1],[Y|L2]):-
div2(L,L1,L2).
concsort([],L,L).
concsort(L,[],L).
concsort([H1|T1],[H2|T2],[H1|T]):-
H1<=H2,!,
concsort(T1,[H2|T2],T).
concsort([H1|T1],[H2|T2],[H2|T]):-
concsort([H1|T1],T2,T).
/* Конец программы */
Упражнение 7.1.
Напишите сортировку методом «пузырька», согласно следующему алгоритму:
% рекурсивное правило bubble:
1. Переставляем первую неупорядоченную пару элементов.
