но не эффективны. Из этих
вставсорт( Хв, УпорХв),
% Сортировка хвоста
встав( 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
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий