[plt-scheme] stable sort
I raised this issue earlier:
http://list.cs.brown.edu/pipermail/plt-scheme/2004-July/006075.html
There is one issue with defining a sort to be stable: one's intuition
would indicate that you need to specify in the interface to the sort
whether it takes a reflexive or an irreflexive relation. This
intuition may be wrong; I've managed to convince myself that you can
hack around your lack of knowledge of whether a relation is reflexive
or irreflexive, as long as it acts in a consistent manner.
I believe that the following reimplementation of mergesort is stable,
though I have not proven it to be so.
It is also a little less efficient than the current implementation of
mergesort in mzlib (it makes some extra calls to the comparator)
(define mergesort/stable
(polymorphic
(lambda (alox less-than)
(letrec ([split (lambda (alox r)
(cond
[(null? alox) r]
[(null? (cdr alox)) (cons alox r)]
[else (split (cdr alox) (cons (list (car alox)) r))]))]
[merge (lambda (l1 l2 r)
(cond
[(null? l1) (append! (reverse! r) l2)]
[(null? l2) (append! (reverse! r) l1)]
[(and (less-than (car l2) (car l1))
(less-than (car l1) (car l2)))
(merge l1 (cdr l2) (cons (car l2) r))]
[(and (not (less-than (car l2) (car l1)))
(not (less-than (car l1) (car l2))))
(merge l1 (cdr l2) (cons (car l2) r))]
[(less-than (car l1) (car l2))
(merge (cdr l1) l2 (cons (car l1) r))]
[else (merge l1 (cdr l2) (cons (car l2) r))]))]
[map2 (lambda (l)
(cond
[(null? l) '()]
[(null? (cdr l)) l]
[else (cons (merge (car l) (cadr l) null)
(map2 (cddr l)))]))]
[until (lambda (l)
(if (null? (cdr l))
(car l)
(until (map2 l))))])
(if (null? alox)
null
(until (split alox null)))))))
On Nov 19, 2004, at 12:36 PM, Shriram Krishnamurthi wrote:
> For list-related administrative tasks:
> http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> There's no stable sort available? I searched for "sort" in Help Desk
> and got
>
> (sort less-than?-proc list) PROCEDURE
> This is the same as mergesort (see section 21) with the arguments
> reversed.
>
> (mergesort list less-than?) PROCEDURE
> Sorts list using the comparison procedure less-than?. This
> implementation is not stable (i.e., if two elements in the input are
> ``equal,'' their relative positions in the output may be reversed).
>
> (quicksort list less-than?) PROCEDURE
> Sorts list using the comparison procedure less-than?. This
> implementation is not stable (i.e., if two elements in the input are
> ``equal,'' their relative positions in the output may be reversed).
>
> S.
>
----
"i'm always going to refer to him as rmfs from now on"
-josh