## Sorting (was Re: How do I do this in dsssl/jade?)

 Subject: Sorting (was Re: How do I do this in dsssl/jade?) From: kubek@xxxxxxxxxxxx (kubek) Date: Tue, 15 Dec 1998 10:17:13 +0100
>>>>> "N.W." == Norman Walsh <ndw@xxxxxxxxxx> writes:

N.W.> / "Glenn R. Kronschnabl" <grk@xxxxxxxxxxxxxxxx> was heard to
N.W.> say: | I have an xml file that looks something like: [...] |
[Q1 snipped ...]

N.W.> Q2: Right now I am sorting/reordering
N.W.> via perl-xml, but I assume I could | reorder the nodelist
N.W.> using dsssl/jade. Anyone have some code I peruse? | | (Q1 is
N.W.> more MUCH more important)

N.W.> Are you saying that all the vcards are already in sorted
N.W.> order? If so, what you want's not too hard. Sorting, that
N.W.> would be a different kettle of fish altogether.

Here is simple code for quicksort able to sort both lists and
node-lists (sorry I forget the initial author for this scheme thing,
maybe in Slib ??).

As sorting a node-list or a simple list is essentially the same
problem, i.e. sort a sequence of elements, there is a first function
(called quicksort::generic) which acts as a "quicksort procedure
maker".

Thid first procedure  defines a general quicksort operation for abstract
sequences defined through the following procedures:
- is-null? tests if the sequence is empty
- first extracts the first element from the sequence
- others gives all the elements from the sequence, except the first
- concat is used for combining two sequences
- empty is the empty sequence

The sorts for list and node-lists are then
defined using this function by :

(define quicksort
(quicksort::generic null? car cdr append cons '()))

(define nl-quicksort
(quicksort::generic node-list-empty?
node-list-first
node-list-rest
node-list
node-list
(empty-node-list)))

(define quicksort::generic
(lambda(is-null? first others concat add empty)
(letrec ((collect
;; Collect is an helper function doing the real work

(lambda (pivot ls lgroup rgroup less?)
(if (is-null? ls)
(concat (impl lgroup less?)
(if (less? pivot (first ls))
(collect pivot (others ls) lgroup
less?)
(collect pivot (others ls)
rgroup
less?)))))
(impl
;; impl first test some trivial sorting case and then call
;; the procedure collect
(lambda (ls less?)
(if (or (is-null? ls) (is-null? (others ls)))
ls
(collect (first ls) (others ls) empty empty less?)))))
;; we return the new defined procedure
impl)))

N.W.>  DSSSList info and archive:
N.W.> http://www.mulberrytech.com/dsssl/dssslist

J.-M.
Computing Center
INSA Toulouse
France

DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist