Quicksort Strikes Again! 
Author Message
 Quicksort Strikes Again!

Quicksort Strikes Again!

    I recently came across a bug in an otherwise excellent Prolog system.
*       DEC-10 Prolog,
*       C Prolog, or
*       Quintus Prolog.
What about other systems?  You'll have to check for yourself.

    The bug is this:  keysort/2 is supposed to be ***STABLE***.
sort/2 and keysort/2 are **indispensable** for efficient Prolog.
The Prolog system I have in mind uses a version of (falsely so-called)
"quick" sort.  The code goes something like this:

        buggy_key_sort(Raw, Sorted) :-
                buggy_key_sort(Raw, Sorted, []).

        buggy_key_sort([], L, L).
        buggy_key_sort([Key-Val|Pairs], L0, L) :-
                key_partition(Pairs, Key, LE, GT),
                buggy_key_sort(LE, L0, [Key-Val|L1]),
                buggy_key_sort(GT, L1, L).

        key_partition([], _, [], []).
        key_partition([Pair|Pairs], Key, [Pair|LE], GT) :-
                key_less_than_or_equal(Pair, Key),
                key_partition(Pairs, Key, LE, GT).
        key_partition([Pair|Pairs], Key, LE, [Pair|GT]) :-
                key_partition(Pairs, Key, LE, GT).

        key_less_than_or_equal(J-_, K) :-

If you have access to the source code of your Prolog system, and the
implementation of keysort/2 looks something like this, rip it out and
replace it by a stable sort.  If you are still hypnotised by the name
"quick" sort, there is a stable version of "quick" sort which is easy
to code in a list-processing language.  (Hint:  see "fat pivot" in the
index of a good book on internal sorting.)  If you aren't hypnotised
by names, replace it by a merge sort; it should be *much* faster, as
well as giving the right answers!

If you haven't got access to the source code of your Prolog system, how
can you tell whether keysort/2 is implemented correctly or not?  Here's
how:  the reason that we care about the stability of keysort/2 is that
if you sort on several keys, you don't want later sorts to disturb the
order created by the earlier sorts.  In the simplest case, we have two
keys.  Try this program.

        swap_keys_and_values([], []).
        swap_keys_and_values([K-V|P], [V-K|S]) :-
                swap_keys_and_values(P, S).

        test :-
                keysort([1-3,1-2,1-1, 2-3,2-2,2-1, 3-3,3-2,3-1], X),
                swap_keys_and_values(X, Y),
                keysort(Y, [1-1,1-2,1-3, 2-1,2-2,2-3, 3-1,3-2,3-3]).

If 'test' fails, you have the bug.

Once again, just to be clear:  QUINTUS PROLOG DOES NOT HAVE THIS BUG.

Mon, 20 Jul 1992 10:27:00 GMT  
 [ 1 post ] 

 Relevant Pages 

1. Dreaded R6003 Divide by 0 Strikes again !


3. [MSW Logo] M$ strikes again

4. [MSW Logo] M$ strikes again

5. The onion truck strikes again ... Announcing rake

6. ANN: MiniRubyWiki has struck again

7. [Fwd: The newbie strikes again]

8. Peter Coffee Strikes Again

9. FPGA Express v3.3 strikes again!

10. The press strikes again...

11. M$ to STRIKE again...

12. M$ to STRIKE again...


Powered by phpBB® Forum Software