How to do quick sort in prolog?
nogo...@my-deja.com
prolog,who can help me?
I use visual prolog,and find a article about how
to do it,but failed.
The article said:
-----------------------------------------
quick sort
Quick sort is one of the fastest sort algorithms.
However, its power is often overvalued. The
efficiency of quick sort is sensitive to choice
of pivot which is used to distribute list into
two "halfs".
quick_sort([],[]).
quick_sort([H|T],Sorted):-
pivoting(H,T,L1,L2),quick_sort
(L1,Sorted1),quick_sort(L1,Sorted2),
append(Sorted1,[H|Sorted2]).
pivoting(H,[],[],[]).
pivoting(H,[X|T],[X|L],G):-X<=H,pivoting(H,T,L,G).
pivoting(H,[X|T],L,[X|G]):-X>H,pivoting(H,T,L,G).
Similarly to merge sort, quick sort exploits the
divide and conquer method of solving problems.
The above implementation of quick sort using
append is not very effective. We can write better
program using accumulator.
quick_sort2(List,Sorted):-q_sort(List,[],Sorted).
q_sort([],Acc,Acc).
q_sort([H|T],Acc,Sorted):-
pivoting(H,T,L1,L2),
quick_sort(L1,Acc,Sorted1),quick_sort
(L1,[H|Sorted1],Sorted)
-----------------------------------------------
I am a beginer user about visual prolog and
don't know how to do it.Would you be so kind to
email me a piece of source code about quick sort
in prolog?Thanks in advance!
Sent via Deja.com http://www.deja.com/
Before you buy.
Yoann Padioleau
> I want to write a program to do quick sort in
> prolog,who can help me?
> I use visual prolog,and find a article about how
> to do it,but failed.
> The article said:
> -----------------------------------------
> quick sort
> Quick sort is one of the fastest sort algorithms.
> However, its power is often overvalued. The
> efficiency of quick sort is sensitive to choice
> of pivot which is used to distribute list into
> two "halfs".
>
> quick_sort([],[]).
> quick_sort([H|T],Sorted):-
> pivoting(H,T,L1,L2),quick_sort
> (L1,Sorted1),quick_sort(L1,Sorted2),
> append(Sorted1,[H|Sorted2]).
in fact it is append(Sorted1,[H|Sorted2], Sorted)
--
Yoann Padioleau, INSA de Rennes, France, http://www.irisa.fr/prive/padiolea
Opinions expressed here are only mine. Je n'écris qu'à titre personnel.
**____ Get Free. Be Smart. Simply use Linux and Free Software. ____**
Matthew M. Huntbach
> I want to write a program to do quick sort in
> prolog,who can help me?
> I use visual prolog,and find a article about how
> to do it,but failed.
> The article said:
> -----------------------------------------
A valid quick sort program
> -----------------------------------------------
> I am a beginer user about visual prolog and
> don't know how to do it.Would you be so kind to
> email me a piece of source code about quick sort
> in prolog?Thanks in advance!
Go back to your article and look at the Prolog code between the
lines of hyphens. This is source code for quick sort in Prolog.
Matthew Huntbach
Fergus Henderson
>nogo...@my-deja.com wrote:
>> I want to write a program to do quick sort in
>> prolog,who can help me?
>> I use visual prolog,and find a article about how
>> to do it,but failed.
...
>Go back to your article and look at the Prolog code between the
>lines of hyphens. This is source code for quick sort in Prolog.
Actually it's not standard Prolog. As well as the missing argument to
append that someone pointed out, it uses `<=' where standard Prolog
code would use `=<'.
In most Prolog systems, the code posted would be quite inefficient,
due to the failure to exploit first-argument indexing (or use cuts)
in the pivoting/4 predicate.
Also quicksort is not the best algorithm to use for sorting lists;
for lists, merge sort is generally a better choice.
--
Fergus Henderson <f...@cs.mu.oz.au> | "I have always known that the pursuit
| of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
Matthew M. Huntbach
> m...@dcs.qmw.ac.uk (Matthew M. Huntbach) writes:
> >nogo...@my-deja.com wrote:
> >> I want to write a program to do quick sort in
> >> prolog,who can help me?
> >> I use visual prolog,and find a article about how
> >> to do it,but failed.
> ...
> >Go back to your article and look at the Prolog code between the
> >lines of hyphens. This is source code for quick sort in Prolog.
> Actually it's not standard Prolog. As well as the missing argument to
> append that someone pointed out, it uses `<=' where standard Prolog
> code would use `=<'.
OK, I didn't look at it closely, but the original message just struck me
as odd. Had it said "this is meant to be code for quick sort but it
isn't working properly" it might have made more sense.
> In most Prolog systems, the code posted would be quite inefficient,
> due to the failure to exploit first-argument indexing (or use cuts)
> in the pivoting/4 predicate.
> Also quicksort is not the best algorithm to use for sorting lists;
> for lists, merge sort is generally a better choice.
Sure, but standard quick sort is one of those algorithms so well known
and understood that I always find "show me how to do quick sort in
this language" is a good starting point for learning any new language.
Matthew Huntbach
Yoann Padioleau
> m...@dcs.qmw.ac.uk (Matthew M. Huntbach) writes:
>
> >nogo...@my-deja.com wrote:
> >> I want to write a program to do quick sort in
> >> prolog,who can help me?
> >> I use visual prolog,and find a article about how
> >> to do it,but failed.
> ...
> >Go back to your article and look at the Prolog code between the
> >lines of hyphens. This is source code for quick sort in Prolog.
>
> Actually it's not standard Prolog. As well as the missing argument to
> append that someone pointed out, it uses `<=' where standard Prolog
> code would use `=<'.
>
> In most Prolog systems, the code posted would be quite inefficient,
> due to the failure to exploit first-argument indexing (or use cuts)
> in the pivoting/4 predicate.
the fact that this algorithm does not modify the structure
"in-place" and so use append is the bottleneck i think.
>
> Also quicksort is not the best algorithm to use for sorting lists;
> for lists, merge sort is generally a better choice.
I always believe that in the average case, quicksort was the fastest
algorithm (not mention radix special sort of course)
erik...@my-deja.com
In article <wi6iton...@merlin.irisa.fr>,
Yoann Padioleau
> i have never gone across merge list algo, any reference plzzz
every books on algorithm talk about merge sort algorithm, the
book from sedgewick, the book from cormen and leiverson, .... check
algorithm on amazon.
Mike Goodrich
>i have never gone across merge list algo, any reference plzzz
>
>In article <wi6iton...@merlin.irisa.fr>,
> Yoann Padioleau <padi...@merlin.irisa.fr> wrote:
>> f...@cs.mu.oz.au (Fergus Henderson) writes:
>>
>> > m...@dcs.qmw.ac.uk (Matthew M. Huntbach) writes:
>> >
>> > >nogo...@my-deja.com wrote:
>> > >> I want to write a program to do quick sort in
>> > >> prolog,who can help me?
>> > >> I use visual prolog,and find a article about how
>> > >> to do it,but failed.
>> > ...
You can find the quicksort in Sterling and Shapiro's book on Prolog.
-mg