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

Голосование закрыто.

Поиск по сайту
Реклама
Обмен электронных валют
money.dn.ua
Статистика

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

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

и не работает

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