Реализация алгоритма быстрой сортировки на Прологе |  |
domains
i=integer
c=symbol
il=i*
cl=c*
predicates
/* сравнение двух значений */
order(i,i)
order(c,c)
/* поиск центрального элемента */
middle(il,il,i,il)
middle(cl,cl,c,cl)
/* разделение списка на два */
split(i,il,il,il)
split(c,cl,cl,cl)
/* соединение двух списков в один */
append(il,il,il)
append(cl,cl,cl)
/* быстрая сортировка */
qsort(il,il)
qsort(cl,cl)
clauses
/* предикат для сравнения двух значений */
order(X,Y):-X<Y.
/*
middle(L, L, X, L1)
Находит в списке L центральный элемент и
возвращает его в Х и список без него в L1.
Невозможно решить эту задачу без введения дополнительного
предиката (например, для подсчёта общей длины) или без
дополнительного аргумента (как в данном случае)
Вариант с аргументом работает быстрее, так как в таком случае
производится один проход по списку, а не два.
В первом аргументе L убираем по два элемента,
а во втором аргументе L - по одному элементу.
Фиксируем факт нахождения среднего элемента,
если первый аргумент - пустой или содержит в себе
ровно один элемент.
*/
middle([],[X|T],X,T).
middle([_],[X|T],X,T).
middle([_,_|T1],[H2|T2],X,[H2|T3]):-
middle(T1,T2,X,T3).
/*
split(X, L, A, B)
Разбивает список L на два подсписка A и B так, что
все элементы А меньше Х, а все элементы В больше Х.
(Куда добавляются элементы, равные Х, не имеет
значения для алгоритма сортировки.
Здесь они (к примеру) добавляются в В.)
*/
split(_, [], [], []).
split(H, [A|X], [A|Y], Z) :-
/* используем механизм отсечений, чтобы не проверять дважды */
order(A, H), !,
split(H, X, Y, Z).
/* это правило может быть применено только в случае,
если not(order(A, H)) - благодаря
использованному отсечению это перепроверять не нужно */
split(H, [A|X], Y, [A|Z]) :-
split(H, X, Y, Z).
/*
append(X,Y,L)
Соединяет два списка в один.
Берём Х, добавляем в конец Y, получаем L.
*/
append([],X,X).
append([H|T],X,[H|T1]):-
append(T,X,T1).
/*
qsort(X,Y)
Быстрая сортировка.
Х - исходный список,
Y - результат
*/
/* если сортируем пустой список, то
результат - пустой список
*/
qsort([], []).
/* собственно, алгоритм быстрой сортировки. */
qsort(L, X) :-
/* находим центральный элемент и удаляем его */
middle(L,L,M,L1),
/* центральный элемент будет разделителем.
разбиваем список без элемента-разделителя на два списка.
*/
split(M, L1, A, B),
/* сортируем по очереди оба списка */
qsort(A, X1),
qsort(B, X2),
/* соединяем отсортированные списки в один.
не забываем поставить разделитель на место.
*/
append(X1,[M|X2],X).
/* если убрать предикат middle и в качестве разделителя всегда выбирать самый первый элемент списка, то второе утверждение для qsort будет таким:
qsort([H|T], X) :-
split(H, T, A, B),
qsort(A, X1),
qsort(B, X2),
append(X1,[H|X2],X).
*/ Последняя модификация: 03.12.07 03:22 q Обсуждение статьи в форуме Не проходите мимо! Оставьте Ваш комментарий в форуме! >>> Просмотреть все комментарии в режиме форума. Всего комментариев: 2
Не проходите мимо! Оставьте Ваш комментарий в форуме! >>> Цитирование материалов моего сайта приветствуется! при условии видимой действующей! гиперссылки на мой сайт. [Ссылки] Если Вы нашли опечатку на этой странице, пожалуйста, выделите ее мышью и нажмите Ctrl+Enter. Сделаем язык чище! (c) Yuri Popoff, 2004 - 2008, popoff.donetsk.ua, style.donetsk.ua
|
|
