Сортировки

Сортировки служат для переупорядочивания элементов определенным образом, для упрощения доступа к нужным элементам.
Рассмотрим четыре простых метода сортировки: 1) наивная, 2) включением, 3) методом пузырька, 4) быстрая.

7.13.1. Наивная сортировка
По этому методу вначале создается некоторая перестановка чисел, затем проверяется, расположена ли она по возрастанию.
Sort(Xs, Ys):-permutation(Xs, Ys),ordered(Ys).
Permutation(Xs, [Z,Zs]):– select(Z, Xs, Ys),permutation(Ys, Zs).
Permutation([ ], [ ]).
Ordered([X]).
Ordered([X, Y|Ys]):-X<=Y, ordered([Y|Ys}).
Наивная_cорт(L1, L2): – перестановка(L1, L2), oтсортировано(L2), !.
Перестановка (L, [H|T]):– присоединить (V, [H|U], L), присоединить (V, U, W), перестановка (W, T).
Перестановка ([  ], [  ]) – граничное условие.
Отсортировано (L): - (0, L) – первый элемент 0.
Отс(_, [  ]).
отс(N, [H|T]): – N<H, отс (H, T).

7.13.2. Сортировка включением
При этой сортировке каждый элемент удаляется из головы списка и передается предикату вклюсор2, который включают его в список и возвращает измененный список.
вклюсор ([  ], [  ]) – граничные условия.
Рекурсивные условия: вклюсор ([Х |L], М): – вклюсор(L, N), вклюсор2(X, N, M).
вклюсор2(X, [Y, L], [Y|M]): – X>Y, !, вклюсор2(X, L, M).
Граничные условия:  вклюсор2(X, L, [X|L]). Это условие соответсвует случаю, когда элемент изначально стоит на своем месте.

7.13.3. Метод «пузырька»
При сортировке по этому методу производится поиск пары соседних элементов, стоящих не по порядку и обмен их местами. Такая операция делается до тех пор, пока такие пары находятся.
Пусорт (L,S): – присоединить (X, [A, B|Y], L), B<A, присоединить(X, [B, A|Y]M), пусорт (M, S).
Граничные условия: пусорт (L, L).
присоединить ([  ], L, L) – граничные условия.
Рекурсивное: присоединить([H|T], L, [H|V]): – присоединить (T, L, V).
Способ отличается от предыдущих необходимостью возвратного хода, поэтому в первом правиле отсечение не используется. Вывод и проверка осуществляется предикатом «Присоединить».

7.13.4. Быстрая сортировка
При быстрой сортировке разделяют список, состоящий из головы Н и хвоста Т на два списка L и M такие, чтобы все элементы из L были меньше или равны H, а все элементы из M больше, чем H. Порядок следования элементов в L и M такой же, как в исходном списке [H|T]. После разбиения применяют быструю сортировку к каждому из списков и присоединяют M к L.
Цель: разбить(H, T, L, M) – разделяет список [H|T] на L и M.
разбить(H, [A|X], [A|Y], Z): – A=<H, разбить(H, X, Y, Z).
разбить(H, [A|X], Y, [A, Z]): – A>H, разбить(H, X, Y, Z).
Граничное условие: разбить( _, [  ], [  ], [  ]).
Граничный случай: бисорт([  ], [  ]).
Рекурсивные условия: бисорт([H|T], S): – разбить(H, T, A, B), бисорт(A, A1), бисорт (В, В1), присоединить(A1, [H|B1], S).