Różnice między wybraną wersją a wersją aktualną.
|
pl:prolog:pllib:merge_sort [2019/06/27 15:50] |
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 ===== | ||
| + | <code prolog> | ||
| + | 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).</code> | ||
| + | ===== Comments ===== | ||
