Quick Sort implemented in Prolog

Last updated on Fri, 2007-12-14 12:44. Originally submitted by fabio on 2007-12-08 15:20.

A Quick Sort implementation written in Prolog.

% Varesano Fabio - QuickSort

/* [+,-] */
quicksort([], []).
quicksort([HEAD | TAIL], SORTED) :- partition(HEAD, TAIL, LEFT, RIGHT),
                                    quicksort(LEFT, SORTEDL),
                                    quicksort(RIGHT, SORTEDR),
                                    append(SORTEDL, [HEAD | SORTEDR], SORTED).

/* [+,+,-,-] */
partition(PIVOT, [], [], []).
partition(PIVOT, [HEAD | TAIL], [HEAD | LEFT], RIGHT) :- HEAD @=< PIVOT,
                                                         partition(PIVOT, TAIL, LEFT, RIGHT).
partition(PIVOT, [HEAD | TAIL], LEFT, [HEAD | RIGHT]) :- HEAD @> PIVOT,
                                                         partition(PIVOT, TAIL, LEFT, RIGHT).

/* [+,+,-] */
append([], LIST, LIST).
append([HEAD | LIST1], LIST2, [HEAD | LIST3]) :- append(LIST1, LIST2, LIST3).
Posted in:

Looks pretty similar

Submitted by Anonymous (not verified) on Sun, 2009-11-22 16:32.

Looks pretty similar to:

http://www.soe.ucsc.edu/classes/cmps203/Spring06/Project/garga/QuickSort...

Actually yes, I probably used

Submitted by fabio on Sun, 2009-11-22 21:31.

Actually yes, I probably used that as inspiration.. or the opposite. Frankly I don't remember.

Pivot

Submitted by Andrew Thomas (not verified) on Sun, 2008-12-14 15:41.

Hi,

I had a go at this and found this article when I was having problems with it. In fact, the structure of my code is almost identical to yours. However, I have a problem in that my pivot function is able to split n elements into a 0 element partition and an n element partition - and then recurse infinitely and run out of stack. This is able to happen because it's possible that the >= test can match with every single element.

I can't spot the difference - what have you done to stop that from being able to happen?

Thanks,

Andy

Why don't you post here your

Submitted by fabio on Sun, 2008-12-14 19:12.

Why don't you post here your code? I will have a look at it.. maybe I can help you troubleshooting..

Btw.. I have to say that I already almost forgot everything about Prolog..

thanks!

Submitted by Mike (not verified) on Tue, 2007-12-18 10:42.

Thanks Fabio for this piece of code.

I was playing with the same things and this helped a lot.

Mike

Post new comment

The content of this field is kept private and will not be shown publicly.
If you have a personal or company website insert its address in the form http://www.example.com/ .
  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd> <pre> <del> <img> <h2> <h3> <h4> <b> <video> <sub> <sup>
  • Lines and paragraphs break automatically.
  • Images can be added to this post.
  • You may use [inline:xx] tags to display uploaded files or images inline.
  • You may insert videos with [video:URL]
  • Each email address will be obfuscated in a human readable fashion or (if JavaScript is enabled) replaced with a spamproof clickable link.

More information about formatting options