# Różnice

Różnice między wybraną wersją a wersją aktualną.

 — pl:prolog:pllib:merge_sort [2019/06/27 15:50] (aktualna) Linia 1: Linia 1: + ====== Merge sort ====== + {{tag>​sorting algorithms recursion}} + ===== Description ===== + Program implements merge sort algorithm. + + **Source**: ​ Guide to Prolog Programming (on-line tutorial) + ===== Download ===== + Program source code: {{merge_sort.pl}} + ===== Listing ===== + + merge_sort([],​[]). ​    % empty list is already sorted + merge_sort([X],​[X]). ​  % single element list is already sorted + merge_sort(List,​Sorted):​- + List=[_,​_|_],​divide(List,​L1,​L2), ​    % list with at least two elements is divided into two parts + merge_sort(L1,​Sorted1),​merge_sort(L2,​Sorted2), ​ % then each part is sorted + mymerge(Sorted1,​Sorted2,​Sorted). ​                 % and sorted parts are merged + mymerge([],​L,​L). + mymerge(L,​[],​L):​-L\=[]. + mymerge([X|T1],​[Y|T2],​[X|T]):​-X=<​Y,​mymerge(T1,​[Y|T2],​T). + mymerge([X|T1],​[Y|T2],​[Y|T]):​-X>​Y,​mymerge([X|T1],​T2,​T). + + + divide(L,​L1,​L2):​-halve(L,​L1,​L2). + + halve(L,​A,​B):​-hv(L,​[],​A,​B). + + hv(L,​L,​[],​L). ​     % for lists of even length + hv(L,​[_|L],​[],​L). ​ % for lists of odd length + hv([H|T],​Acc,​[H|L],​B):​-hv(T,​[_|Acc],​L,​B).​ + ===== Comments =====
pl/prolog/pllib/merge_sort.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)