--- pl:prolog:pllib:diff_quicksort [2019/06/27 15:50]
+++ pl:prolog:pllib:diff_quicksort [2019/06/27 15:50] (aktualna)
@@ Linia 1: / Linia 1: @@
+====== Diff quicksort ======
+{{tag>lists sorting}}
+===== Description =====
+Quicksort using difference-list
+**Source**:  The Art of Prolog
+===== Download =====
+Program source code: {{diff_quicksort.pl}}
+===== Listing =====
+<code prolog>
+/*
+    quicksort(List,Sortedlist) :-
+	Sortedlist is an ordered permutation of list.
+*/
+	:- op(40,xfx,\).
+	quicksort(Xs,Ys) :- quicksort_dl(Xs,Ys\[]).
+	quicksort_dl([X|Xs],Ys\Zs)  :-
+		partition(Xs,X,Littles,Bigs),
+		quicksort_dl(Littles,Ys\[X|Ys1]),
+		quicksort_dl(Bigs,Ys1\Zs).
+	quicksort_dl([],Xs\Xs).
+	partition([X|Xs],Y,[X|Ls],Bs) :-
+	   X =< Y, !, partition(Xs,Y,Ls,Bs).
+	partition([X|Xs],Y,Ls,[X|Bs]) :-
+	   X > Y, !, partition(Xs,Y,Ls,Bs).
+	partition([],Y,[],[]).
+%	Program 15.4: Quicksort using difference-lists.
+</code>
+===== Comments =====

pl/prolog/pllib/diff_quicksort.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)

AIwiki

Menu