Diff quicksort

Description

Quicksort using difference-list

Source: The Art of Prolog

Download

Program source code: diff_quicksort.pl

Listing

/*	
    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.

Comments

pl/prolog/pllib/diff_quicksort.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0