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

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

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

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

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

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

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

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

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

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

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

line();

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

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

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