Программирование на языке ПРОЛОГ для искуственного интеллекта




Сортировка списков - часть 2


                пузырек( Спис1, УпорСпис).

        пузырек( УпорСпис, УпорСпис).
                                        % Если нет, то список уже упорядочен

        перест( [Х, Y | Остаток], [Y, Х ) Остаток] ):-
                                    % Перестановка первых двух элементов
                больше( X, Y).

        перест( [Z | Остаток], [Z | Остаток1] ):-
                перест( Остаток, Остаток1).
        % Перестановка в хвосте

Еще один простой алгоритм сортировки называется сортировкой со вставками. Он основан на следующей идее:

line();

Для того, чтобы упорядочить непустой список  L = [X | Хв],  необходимо:

(1)        Упорядочить хвост  Хв   списка  L.

(2)        Вставить голову  Х  списка  L  в упорядоченный хвост, поместив ее в такое место, чтобы получившийся список остался упорядоченным. Список отсортирован.

line();

Этот алгоритм транслируется в следующую процедуру вставсорт на Прологе:

        вставсорт([ ], [ ]).

        вставсорт( [X | Хв], УпорСпис) :-
                вставсорт( Хв, УпорХв),
                    % Сортировка хвоста



Содержание  Назад  Вперед