[Закрыть]
 
popoff.donetsk.ua
Добро никогда не остаётся безнаказанным.
Начало | Новости | Статьи | Форум | Опросы | Карта сайта | Обо мне
popoff.donetsk.ua - Статьи - ДонНТУ - Функциональное и логическое программирование - Реализация алгоритма быстрой сортировки на Прологе
Я это делаю
Персональное меню
Голосование
Деньги, либо любимое занятие? Постоянный адрес этого вопроса
Ваш возраст (не обязательно):

Введите целое число от 3 до 99.
Почему? (не обязательно):
Другие вопросы
Поиск по сайту
Реклама
Гинеколог, стоматолог, психотерапевт в Донецке
Статистика

Реализация алгоритма быстрой сортировки на Прологе

Постоянный адрес статьи
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

Обсуждение статьи в форуме

Не проходите мимо! Оставьте Ваш комментарий в форуме! >>>

14.04.09 14:31 Arslan

Очень пояснительно...

24.05.12 12:32 Надюш

и не работает

10.11.18 14:36 Natine123

Какая жалость...

Просмотреть все комментарии в режиме форума. Всего комментариев: 3
Не проходите мимо! Оставьте Ваш комментарий в форуме! >>>