Предикат сортировки в Прологе

В SWI-Prolog sort/2 является «встроенным», поэтому он есть в C.

Файл вроде бы src/pl-lists.c из раздачи.

Вот:

https://github.com/SWI-Prolog/swipl-devel/blob/master/src/pl-list.c

В строке 543:

static
PRED_IMPL("sort", 2, sort, PL_FA_ISO)
{ PRED_LD

  return pl_nat_sort(A1, A2,
             TRUE, SORT_ASC,
             0, NULL, FALSE PASS_LD);
}

pl_nat_sort находится в том же файле

Комментарий исторически интересен:

Естественная сортировка слиянием. Код предоставлен Ричардом О'Кифом и интегрирован в SWI-Prolog Яна Вилмейкера. Приятным моментом в этом коде является что он не использует дополнительное пространство и довольно стабилен в производительности. Ричардс утверждает, что многие реализации qsort() в libc очень медленный. Это не относится к glibc 2.2, где производительность примерно так же, как предыдущая реализация на основе qsort().

Предположительно Ричард О'Киф отмечает:

Я использую вариант этого кода в утилите сортировки примерно с 1988. Он оставляет программу sort(1) в UNIX далеко позади. Как ты можешь знать, sort(1) разбивает ввод на блоки, которые помещаются в памяти, сортирует блоков с помощью qsort() и записывает блоки на диск, а затем объединяет блоки. Для файлов, помещающихся в память, выполняется вариант этого кода примерно в два раза быстрее, чем sort(1). Отчасти это лучший ввод-вывод, но отчасти просто не используя qsort().

Даюм. Это навевает воспоминания о написании алгоритмов сортировки в 89-м.

Попробуйте выполнить поиск по быстрой сортировке.

Вот одна ссылка: https://www.codepoc.io/blog/prolog/4934/prolog-program-to-sort-a-list-using-quick-sort

Вот еще один пример: -

quicksort([], []).
quicksort([X | Tail], Sorted):-
    split(X, Tail, Small, Big),
    quicksort(Small, SortedSmall),
    quicksort(Big, SortedBig),
    concatenate(SortedSmall, [X| SortedBig], Sorted).

split(X, [], [], []).
split(X, [Y| Tail], [Y | Small], Big):-
    X > Y, !,
    split(X, Tail, Small, Big).
split(X, [Y| Tail], Small, [Y | Big]):-
    split(X, Tail, Small, Big).

concatenate([],List,List).
concatenate([Item|List1],List2,[Item|List3]) :-
    concatenate(List1,List2,List3).


?-quicksort([1,7,4,3,6,5,9,8,12,1],L).
L = [1, 1, 3, 4, 5, 6, 7, 8, 9, 12]
false

Если вы просто ищете какой-либо алгоритм сортировки, вы всегда можете использовать пузырьковую сортировку *кашель*. Это один из самых простых и неэффективных способов сортировки списка, но, в зависимости от реализации, он будет проходить через уже отсортированный список за линейное время. Пузырьковая сортировка не удаляет дубликаты. Эта реализация выполняет порядок убывания:

bubblesort(List, SortedList) :-
    bubbleit(List, List1), 
    ! ,
    bubblesort(List1, SortedList) .
bubblesort(List, List).

bubbleit([X,Y|Rest], [Y,X|Rest]) :-
    X < Y, 
    ! .
bubbleit([Z|Rest], [Z|Rest1]) :-
    bubbleit(Rest, Rest1).

?- bubblesort([1,2,5,4,7,3,2,4,1,5,3],L).
L = [7, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1].

Если вы хотите отсортировать второй элемент в списке [_,E|], измените первое bubbleit правило на

bubbleit([X,Y|Rest], [Y,X|Rest]) :-
    X = [_,XX|_],
    Y = [_,YY|_],
    XX < YY, 
    ! .

?- bubblesort([[a,3],[b,5],[c,1],[d,4]],L).
L = [[b, 5], [d, 4], [a, 3], [c, 1]].

Алгоритм сортировки слиянием естественно подходит для Пролога. Не говоря уже о тривиальной реализации на языке с рекурсией и списками в качестве фундамента.

Вот игровая площадка SWI: https://swish.swi-prolog.org/p/swi-prolog-merge-sort.pl

merge_sort( [], [] ).             % The empty list is by definition ordered
merge_sort( [X], [X] ).           % So is a list of length one
merge_sort( Unsorted, Sorted ) :- % otherwise...
  partition( Unsorted, L, R ) ,   % partition the list into 2 halves
  merge_sort(L,L1),               % recursively sort the left half
  merge_sort(R,R1),               % recursively sort the right half
  merge(L1,R1,Sorted)             % merge the newly-sorted halves
    .                             % See? simple!

partition( []      , []     , []     ).   % the empty list gets partitioned into two empty lists
partition( [X]     , [X]    , []     ).   % a left of length 1 gets partitioned into itself and an empty list
partition( [X,Y|L] , [X|Xs] , [Y|Ys] ) :- % list of length 2 or more gets popped and divided between left and right halves
  partition(L,Xs,Ys)                      % with the remainder being recursively partitioned.
    .                                     % Easy!

merge( []     , []     , []     ).        % merging to empty lists is trivial
merge( []     , [Y|Ys] , [Y|Ys] ).        % merging an empty list and a non-empty list is easy
merge( [X|Xs] , []     , [X|Xs] ).        % merging a non-empty list and an empty list is easy
merge( [X|Xs] , [Y|Ys] , [Lo,Hi|Zs] ) :-  % otherwise...
  compare(X,Y,Lo,Hi),                     % compare the two terms, put them in collating sequence
  merge(Xs,Ys,Zs)                         % and recursively merge the tails
  .                                       % Easy!

compare( X , Y , X, Y ) :- X @=< Y. % if X <= Y, X is Lo, and Y is Hi
compare( X , Y , Y, X ) :- X @>  Y. % if X >  Y, Y is Lo, and X is Hi