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



         

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


line();

        быстрсорт( Спис, УпорСпис) :-

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

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

        быстрсорт2( [X | Хвост], A1-Z2) :-

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

                быстрсорт2( Меньш, А1-[Х | A2] ),

                быстрсорт2( Больш, A2-Z2).

line();

Рис. 9. 3.  Более эффективная реализация процедуры быстрсорт

с использованием разностного представления списков. Отношение

разбиение( Х, Спис, Меньш, Больш)

определено, как на рис. 9.2.

быстрсорт2. Здесь, как и раньше, процедура быстрсорт использует обычное представление списков, но в действительности сортировку выполняет более эффективная процедура быстрсорт2, использующая разностное представление. Эти две процедуры связаны между собой, соотношением

        быстрсорт( L, S) :-

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




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