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



         

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


                 % Полезная перестановка ?

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

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

                                        % Если нет, то список уже упорядочен

        перест( [Х, Y | Остаток], [Y, Х ) Остаток] ):-

                                    % Перестановка первых двух элементов

                больше( X, Y).

        перест( [Z | Остаток], [Z | Остаток1] ):-

                перест( Остаток, Остаток1).        % Перестановка в хвосте

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

Он основан на следующей идее:

line();

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

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

  списка  L.

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

line();

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

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

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



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