Różnice między wybraną wersją a wersją aktualną.
|
pl:prolog:pllib:merge_sort_2 [2019/06/27 15:50] |
pl:prolog:pllib:merge_sort_2 [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| + | ====== Merge sort 2 ====== | ||
| + | {{tag> sorting algorithms recursion}} | ||
| + | ===== Description ===== | ||
| + | Program implements merge sort algorithm. | ||
| + | |||
| + | **Source**: PrologTutorial (on-line tutorial) | ||
| + | ===== Download ===== | ||
| + | Program source code: {{merge_sort_2.pl}} | ||
| + | ===== Listing ===== | ||
| + | <code prolog> | ||
| + | mergesort([],[]). /* covers special case */ | ||
| + | mergesort([A],[A]). | ||
| + | mergesort([A,B|R],S) :- | ||
| + | split([A,B|R],L1,L2), | ||
| + | mergesort(L1,S1), | ||
| + | mergesort(L2,S2), | ||
| + | mymerge(S1,S2,S). | ||
| + | |||
| + | split([],[],[]). | ||
| + | split([A],[A],[]). | ||
| + | split([A,B|R],[A|Ra],[B|Rb]) :- split(R,Ra,Rb). | ||
| + | |||
| + | mymerge(A,[],A). | ||
| + | mymerge([],B,B). | ||
| + | mymerge([A|Ra],[B|Rb],[A|M]) :- A =< B, mymerge(Ra,[B|Rb],M). | ||
| + | mymerge([A|Ra],[B|Rb],[B|M]) :- A > B, mymerge([A|Ra],Rb,M). | ||
| + | |||
| + | % ?- mergesort([4,3,6,5,9,1,7],S). | ||
| + | % S=[1,3,4,5,6,7,9] | ||
| + | </code> | ||
| + | ===== Comments ===== | ||
