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

Question

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.

Solution

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.

Comments

[ChrisF]

The default IP address for home routers is usually 192.168.2.1.

[heavyd]

@ChrisF the routers I've seen usually have 192.168.0.1 or 192.168.1.1, but never 192.168.2.1. And the fact that its asking for a username/password leads to believe that it is connecting to something.

[ChrisF]

@heavyd - mine's 192.168.2.1. Interesting.

[ChrisF]

@Sotiris what IP do you use to connect to the web interface?

[heavyd]

@Sotiris also, what model of router do you have?

[Sotiris]

I own a baudTec router (I don't know exactly the model). I connect on web interface through 192.168.1.1

[LostLin]

possible duplicate of Sorting list of pairs by the second element of the pairs in scheme

[John Friedrich]

Can someone please write this function without using a built in scheme function? or is it IMPOSSIBLE?

[Claudiu]

@JohnFriedrich: step 1) write a sort function that takes a 'cmp' parameter. step 2) call it with a 'cmp' parameter that compares the second element of lists. so your question reduces simply to, how to write a sort function in scheme?

[John Friedrich]

Do I then iterate through the list the amount of times equal to the length of the list?

[John Friedrich]

This just makes me extremely disappointed.

[C. K. Young]

@JohnFriedrich There are sorting algorithms that are faster than O(n²), so no need to be extremely disappointed. (The fastest ones have O(n log n) worst-case time; I believe it's impossible to go any faster.)

[Will Ness]

@ChrisJester-Young surely you forgot about en.wikipedia.org/wiki/Integer_sorting ... :)

[C. K. Young]

@WillNess Nice! Thanks for the heads-up. :-)

[Mark]

Are you trying to access files stored on a SMB share connected to your router or do you want to actually get the image (operating system) that your router uses to boot?

[John Friedrich]

Thanks, this looks more like something I can understand since I am relatively new to Scheme.