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


         

но не эффективны. Из этих



                вставсорт( Хв, УпорХв),

                    % Сортировка хвоста

                встав( X, УпорХв, УпорСпис).

                                                        % Вставить Х на нужное место



Рис. 9. 1.  Сортировка списка процедурой быстрсорт.

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

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

                встав( X, УпорСпис, УпорСпис1).


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

Процедуры сортировки пузырек и вставсорт

просты, но не эффективны. Из этих двух процедур процедура со вставками более эффективна, однако среднее время, необходимое для сортировки списка длиной  n  процедурой вставсорт, возрастает с ростом n пропорционально  n2.   Поэтому для длинных списков значительно лучше работает алгоритм быстрой сортировки, основанный на следующей идее (рис. 9.1):

line();

Для того, чтобы упорядочить непустой список  L,   необходимо:

(1)        Удалить из списка  L

 какой-нибудь элемент  Х  и разбить оставшуюся часть на два списка, называемые Меньш и Больш, следующим образом: все элементы большие, чем  X,   принадлежат списку Больш, остальные - списку Меньш.


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





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