становится тривиальной операцией после применения

                конк( УпорМеньш, [X | УпорБольш], УпорСпис).

        разбиение( X, [ ], [ ], [ ] ).

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

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

                разбиение( 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 под именем


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

---

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий

---

---

---