Ответ в теме: Быстрая сортировка на Prolog

      Комментарии к записи Ответ в теме: Быстрая сортировка на Prolog отключены
#2084

Более подробное описание и асимптотические анализ алгоритма быстрой сортировки можно посмотреть в специальной статье.

qsort([], []).
qsort([Elem], [Elem]).
qsort([Pivot|Tail], SortedList):-
  divide(Tail, Pivot, GreaterList, SmallerList),
  qsort(GreaterList, SortedGreaterList),
  qsort(SmallerList, SortedSmallerList),!,
  append(SortedSmallerList, [Pivot|SortedGreaterList], SortedList).

Первое правило обрабатывает случай, когда на вход подан пустой список, а второе обрабатывает список из одного элемента. Такие списки уже отсортированы, поэтому результатом является точно такой же список.
В противном случае из списка выделяется первый элемент, который берется в качестве опорного, функцией divide список разделяется на две части. Все элементы в левой части гарантированно меньше элементов второй части, поэтому после их рекурсивной сортировки мы можем использовать обычное соединение списков, при котором «больший» список дописывается в конец «меньшего».