CODEWITHSUNDEEP
listsortingscheme
John Friedrich
John Friedrich

Reputation: 343

Sorting a list of pairs based on the second element in Scheme

Can someone give me some advice as to how to go about writing code to sort a list of pairs in increasing order based on the second element of each of the pairs? I don't have an example for you, but this seems like a simple thing to imagine.

Upvotes: 0

Views: 858

Answers (1)

Will Ness
Will Ness

Reputation: 71065

Let's try to write a mergesort. 

(define (mgsort ls cmp)
  (cond
    ((or (null? ls) (null? (cdr ls)))
       ls)
    ; right? ... then,
    (else 
      (split ls '() '() cmp))))

The most basic tool in dealing with lists is structural recursion:

(define (split ls a b cmp)
  (cond 
    ((null? ls) 
       (merge (mgsort a cmp) (mgsort b cmp) cmp))
    (else
       (split (cdr ls) b (cons (car ls) a) cmp))))

What's left now it just to write merge – a function that will merge, like "zipping", its two arguments which are sorted lists, so the result is a sorted list too.

(define (merge a b cmp)
  (cond 
    ((null? a) b)
    ((null? b) ....)
    ((cmp (car a) (car b))   ; right?
       (cons   
          ... ;; what? ... with what??
          (merge (cdr a) ......)))
    (else
       (cons
          ... 
          (merge a ......)))))

Testing:

(mgsort (list 3 1 5 4 6 2 3) <)
;Value 12: (1 2 3 3 4 5 6)

(mgsort (list (cons 3 1) (cons 4 5) (cons 6 2)) (lambda(a b) (< (cdr a) (cdr b))))
;Value 13: ((3 . 1) (6 . 2) (4 . 5))

cf. how would one merge two strings that are ordered alphabetically in lisp using recursion for an efficient top-down merge function (though in Common Lisp, and nominally for strings, but it really works with lists inside), a by-hand implementation of tail recursion modulo cons optimization technique.

Upvotes: 1

Related Questions