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




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



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

становится тривиальной операцией после применения разностного представления списков, введенного в гл. 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, Хвост, Меньш, Больш),
                быстрсорт2( Меньш, А1-[Х | A2] ),
                быстрсорт2( Больш, A2-Z2).

line();









Начало  Назад  Вперед