sort question 
Author Message
 sort question

Hello!

I want to sort lists ( or some kind of data structudes ) inside a list
according to the first, second, third... item in the lists/structures.
Can sort be used? or can someone point te to functions that can do the
job, or some place to read about it.

Thanks
Bo



Mon, 12 Apr 2004 09:45:17 GMT  
 sort question

Quote:

> Hello!

> I want to sort lists ( or some kind of data structudes ) inside a list
> according to the first, second, third... item in the lists/structures.
> Can sort be used?

Well which sort are you talking about?

There is not standard sort for Schemes. But there are quite a lot of
sort functions available. It usually takes at least two parameters a
sequence to sort and a function to which the sort should take place
accordingly. Well you can role you own comparison function than.

along this lines:

(define (my-< a b)
  (cond
    ((or (null? a) (null? b))
     (cond
       ((and (null? a) (null? b)) #f)
       ((null? a) #t)
       (else
        #f)))
    ((< (car a) (car b)) #t)
    ((> (car a) (car b)) #f)
    (else
     (my-< (cdr a) (cdr b)))))    

If you now sort a list of lists you'll with
(sort my-< '((1 2 3) (1 1 2) (1 1 1)))
((1 1 1) (1 1 2) (1 2 3))

(sort my-< '((1 2) (1 1) (1 1 2)))
((1 1) (1 1 2) (1 2))

Regards
Friedrich



Mon, 12 Apr 2004 14:09:38 GMT  
 sort question
This will be a very fast sort which takes a predicate in a  list.....
Your procedure should call mergesort with the car of your input and the cdr
of your input:

(define sort-by
   (lambda (ls)
      (mergesort (eval (car ls)) (cdr ls))))

(define mergesort
  (lambda (pred ls)
    (define merge
      (lambda (ls1 ls2)
        (if (null? ls1)
            ls2
            (if (null? ls2)
                ls1
                (if (pred (car ls1) (car ls2))
                    (cons (car ls1) (merge (cdr ls1) ls2))
                    (cons (car ls2) (merge ls1 (cdr ls2))))))))
    (define list-head
      (lambda (ls n)
        (if (zero? n)
            '()
            (cons (car ls)
                  (list-head (cdr ls) (sub1 n))))))
    (let ([len (length ls)])
      (let ([midpoint (quotient len 2)])
        (if (<= len 1)
            ls
            (merge (mergesort pred (list-head ls midpoint))
                   (mergesort pred (list-tail ls midpoint))))))))

So...you can call :

Quote:
>(sort-by '(string<=? "jaguar" "iguana" "rabbit" "jackal" "penguin"

"anteater"))

and expect to see:

("anteater" "iguana" "jackal" "jaguar" "penguin" "rabbit")

hope this helps!

Bob


Quote:
> Hello!

> I want to sort lists ( or some kind of data structudes ) inside a list
> according to the first, second, third... item in the lists/structures.
> Can sort be used? or can someone point te to functions that can do the
> job, or some place to read about it.

> Thanks
> Bo



Mon, 12 Apr 2004 14:56:37 GMT  
 sort question

Quote:

>Hello!

>I want to sort lists ( or some kind of data structudes ) inside a list
>according to the first, second, third... item in the lists/structures.
>Can sort be used? or can someone point te to functions that can do the
>job, or some place to read about it.

It's a bit vague what you're trying to do. Can you be a bit more
precise?

I understand that you want to sort a list of lists, using the n-th
element of each list as a sort key.

First, you could get a general sorting function with a user-defined
sorting predicate, like so:

  (define (join-sorted <= l1 l2)
    (cond
      ((null? l1)
       l2)
      ((null? l2)
       l1)
      (else
       (let ((h1 (car l1))
             (h2 (car l2)))
         (if (<= h1 h2)
             (cons h1 (join-sorted <= (cdr l1) l2))
             (cons h2 (join-sorted <= l1 (cdr l2))))))))

  (define (split lst)
    (define (helper lst1 lst2 lst)
      (if (null? lst)
          (values lst1 lst2)
          (helper (cons (car lst) lst2) lst1 (cdr lst))))
    (helper '() '() lst))

  (define (sort <= l)
    (cond
      ((or (null? l)
           (null? (cdr l)))
       l)
      (else
       (let-values (((l1 l2) (split l)))
         (join-sorted <= (sort <= l1) (sort <= l2))))))

E.g. (sort <= '(3 5 1 2)) ==> (1 2 3 5)

Then you define a sort predicate that compares the n-th element.

(define (make<= <= n)
   (lambda (l1 l2)
     (<= (list-ref l1 n) (list-ref l2 n))))

Now you can do:

 (sort (make<= <= 1) '((foo 3) (bar 1) (baz 5) (qux 2)))

==>

 ((bar 1) (qux 2) (foo 3) (baz 5))

Greetings,

Stephan



Mon, 12 Apr 2004 15:06:12 GMT  
 sort question

Quote:

> It's a bit vague what you're trying to do. Can you be a bit more
> precise?

Well... a list of race horses in a race.  Then I want for exaple  startnr or
odds be the sort keys.

(define horse (startnr name odds possybly-other-vars))

(define a-race ((1 Moneymaker 36 ... ) (2 Varenne 12 ...) ...)

(sort startnr<  a-race ) ==> ((1 Moneymaker 36) (2 Varenne 12) ...)
(sort odds<  a-race) ==> ((2 Varenne 12) (1 Moneymaker 36)...)

A first look at Your example seems to be what I try to do, but whan I tried
it,  scheme complained about Unbound variable: let-values.  I shall take a
closer look at it later.

Thanks
Bo



Tue, 13 Apr 2004 00:06:59 GMT  
 sort question

Quote:

> First, you could get a general sorting function with a user-defined
> sorting predicate, like so:

>   (define (join-sorted <= l1 l2)
>     (cond

<snip>

I found this similar to the example in The Scheme programming Language, and
that example is similar to sort in slib....

Quote:

> Then you define a sort predicate that compares the n-th element.

> (define (make<= <= n)
>    (lambda (l1 l2)
>      (<= (list-ref l1 n) (list-ref l2 n))))

I tried this one with slib...

Quote:

> Now you can do:

>  (sort (make<= <= 1) '((foo 3) (bar 1) (baz 5) (qux 2)))

but slib have the predicate at the end.

(require 'sort)

(define (make<= <= n)
   (lambda (l1 l2)
     (<= (list-ref l1 n) (list-ref l2 n))))

 (sort '((foo 3) (bar 1) (baz 5) (qux 2)) (make<= <= 1))  ==> ((bar 1) (qux 2)
(foo 3) (baz 5))

Thanks!
Bo



Tue, 13 Apr 2004 04:02:13 GMT  
 sort question

Quote:

>A first look at Your example seems to be what I try to do, but whan I tried
>it,  scheme complained about Unbound variable: let-values.  I shall take a
>closer look at it later.

Oops, sorry. let-values is indeed not standard Scheme; it is a common
extension, and I use it a lot (it is described at
http://srfi.schemers.org/srfi-11/srfi-11.html ). It's sad that there
are still Schemes that don't implement it ;-)

Anyway, here is the sort procedure without let-values:

  (define (sort <= l)
    (cond
      ((or (null? l)
           (null? (cdr l)))
       l)
      (else
        (call-with-values
          (lambda () (split l))
          (lambda (l1 l2)
            (join-sorted <= (sort <= l1) (sort <= l2)))))))

Greetings,

Stephan



Tue, 13 Apr 2004 15:34:18 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Listbox sorting question

2. Another sorting question

3. CW2003 Browse Sort Question

4. newbie locale/ascii sort question

5. Sort Question

6. Sort Question

7. Homework: Sorting Question

8. Sort question

9. a sorting question...

10. sorting question

11. list sort question

12. List sorting question

 

 
Powered by phpBB® Forum Software