Quicksort (Prolog)


Implementation in C++, can be found here.

/* quicksort(Xs, Ys) is true if Ys is a sorted permutation of the list Xs. */
quicksort(Xs, Ys):-quicksort_1(Xs, Ys, []).
quicksort_1([], Ys, Ys).
quicksort_1([X|Xs], Ys, Zs):-
  partition(Xs, X, Ms, Ns),
  quicksort_1(Ns, Ws, Zs),
  quicksort_1(Ms, Ys, [X|Ws]).
/* partition(Ls, X, Ms, Ns) is true if the list Ms contains the elements   */
/*   of the list Ls which are less than or equal to X, and the list Ns     */
/*   contains the elements of Ls which are greater than X.                 */
partition([K|L], X, M, [K|N]):-
  X < K, !,
  partition(L, X, M, N).
partition([K|L], X, [K|M], N):-
  partition(L, X, M, N).
partition([], _, [], []).

The code comes from here.

Have questions about this code? Comments? Did you find a bug? Let me know! 😀
Page created by G. (George) Samaras (DIT)


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s