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




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


                разбиение( X, Хвост, Меньш, Больш).

        разбиение( X, [Y | Хвост], Меньш, [Y | Больш] ) :-
                разбиение( X, Хвост, Меньш, Больш).

        конк( [ ], L, L).

        конк( [X | L1], L2, [X | L3] ) :-
                конк( L1, L2, L3 ).

line();

Рис. 9. 2.  Быстрая сортировка.

становится тривиальной операцией после применения разностного представления списков, введенного в гл. 8. Для того, чтобы использовать эту идею в нашей процедуре сортировки, нужно представить встречающиеся в ней списки в форме пар вида A-Z следующим образом:

        УпорМеньш имеет вид A1-Z1
        УпорБольш имеет вид A2-Z2

Тогда конкатенации списков

        УпорМеньш и [ Х | УпорБольш]

будет соответствовать конкатенация пар

        A1-Z1    и     [ Х | A2]-Z2

В результате мы получим

        А1-Z2,     причем    Z1 = [ Х | А2]

Пустой список представляется парой Z-Z. Систематически вводя изменения в программу рис. 9.2, мы получим более эффективный способ реализации процедуры быстрсорт, показанный на рис. 9.3 под именем

line();

        быстрсорт( Спис, УпорСпис) :-
                быстрсорт2( Спис, УпорСпис-[ ] ).

        быстрсорт2( [ ], Z-Z).

        быстрсорт2( [X | Хвост], A1-Z2) :-
                разбиение( X, Хвост, Меньш, Больш),



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