This is the mail archive of the guile@cygnus.com mailing list for the guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: stable sorting


Klaus.Schilling@home.ivm.de writes:

> Emacs Lisp comes with a sort routine that is stable, i.e. the order of 
> objetcs that are indistinguishable by the used sorting criterion is 
> unaltered by the sorting process and thus remains the same as in the
> input list.
> 
> Is it easy to provide something similar for guile?

If you have installed slib, you can do

  (use-modules (ice-9 slib))
  (require 'sort)

to get a stable `sort'.

However, Roland Orre has written a sort.c which almost implements
slib's sort interface in C.  I will add this code to libguile within a
couple of days.  (When/if libguile is factorized, the sort routines
will go into a separate module.)

The interface is identical to slib's except that `sort' and `sort!'
are unstable.  In addition, there will be a couple of procedures
`stable-sort' and `stable-sort!'.  We will also provide aliases
`sort-list' and `sort-list!' for compatibility with scsh.

The rationale behind this choice of interface is the following:

In applications which work with large amounts of data it is essential
that we can sort the data "in place".  Stable algorithms usually
require O(N) extra space and significant extra time to execute.

As noted above, we will be compatible with scsh.  In order to maintain
100% compatibility with slib we would have to rename `sort' to
`unstable-sort' and `stable-sort' to `sort'.  We refrain from this
since it seems more natural that the added constraint of stability
results in an added prefix in the name, and since it would be annoying
to use the long name `unstable-sort' for the majority of cases, where
stability isn't required.

/mdj