From: mtheodore
Subject: Newbie Sorting Problem A novice in the ways of Lisp, I'm not sure how to use #'sort to sort on multiple fields. Could someone please enlighten me as to how I would sort the following list (((2 3) (3 11) (4 2) (5 1)) ((2 0) (3 9) (4 0) (5 5)) ((2 3) (3 10) (4 4) (5 0)) ((2 2) (3 0) (4 2) (5 8)) ((2 2) (3 12) (4 3) (5 0)) ((2 2) (3 0) (4 7) (5 4))) to arrive at the following result? (((2 0) (3 9) (4 0) (5 5)) ((2 2) (3 0) (4 2) (5 8)) ((2 2) (3 0) (4 7) (5 4)) ((2 2) (3 12) (4 3) (5 0)) ((2 3) (3 10) (4 4) (5 0)) ((2 3) (3 11) (4 2) (5 1))) (In other words, with each list in the list of lists, one sorts on the second element of the first sub-list. If this is a tie, then one one sorts on the second element of the second sub-list, etc.) All who respond will live a life which is blissfully free of parenthesis problems! thanks in advance, Michael
Date:
Message-ID: <36ED6463.77D280EE@uswest.net>
Content-Type: text/plain; charset=us-ascii; x-mac-type="54455854"; x-mac-creator="4D4F5353"
Content-Transfer-Encoding: 7bit
Dear Lispers,
A novice in the ways of Lisp, I'm
not sure how to use #'sort to sort
on multiple fields. Could someone
please enlighten me as to how
I would sort the following list
(((2 3) (3 11) (4 2) (5 1))
((2 0) (3 9) (4 0) (5 5))
((2 3) (3 10) (4 4) (5 0))
((2 2) (3 0) (4 2) (5 8))
((2 2) (3 12) (4 3) (5 0))
((2 2) (3 0) (4 7) (5 4)))
to arrive at the following result?
(((2 0) (3 9) (4 0) (5 5))
((2 2) (3 0) (4 2) (5 8))
((2 2) (3 0) (4 7) (5 4)) ;we had to look at the third sub-list for this
one
((2 2) (3 12) (4 3) (5 0))
((2 3) (3 10) (4 4) (5 0))
((2 3) (3 11) (4 2) (5 1)))
(In other words, with each list in the
list of lists, one sorts on the second
element of the first sub-list. If this is
a tie, then one one sorts on the second
element of the second sub-list, etc.)
All who respond will live a life which
is blissfully free of parenthesis problems!
thanks in advance,
Michael
PS -BTW, Any guess on what the lists
represent?
In article <·················@uswest.net>,
mtheodore <·········@uswest.net> wrote:
>Dear Lispers,
>A novice in the ways of Lisp, I'm
>not sure how to use #'sort to sort
>on multiple fields.
SORT requires you to supply the comparison function. So you write a
predicate that compares the first field; if they're equal, it then compares
the second field, and so on.
For your particular problem, the function would be:
(defun compare-sublists (list1 list2)
(cond ((null list1)
(not (null list2))) ; a shorter list is considered lower
((null list2) nil)
((< (second (car list1)) (second (car list2)))
t)
((> (second (car list1)) (second (car list2)))
nil)
;; first sublists are equal, so recurse on the rest
(t (compare-sublists (cdr list1) (cdr list2)))))
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
mtheodore <·········@uswest.net> writes:
> A novice in the ways of Lisp, I'm not sure how to use #'sort to sort
> on multiple fields. Could someone please enlighten me as to how I
> would sort the following list [...]
As with any problem of this kind, reduce your problem to figuring out
how to get two elements in the right order. The rest will follow.
For example, to sort by first and last name, you might write:
(defun name-lessp (name1 name2)
(destructuring-bind (family-name-1 personal-name-1) name1
(destructuring-bind (family-name-2 personal-name-2) name2
(or (string-lessp family-name-1 family-name-2)
(and (string-equal family-name-1 family-name-2)
(string-lessp personal-name-1 personal-name-2))))))
Then you should be able to do
(sort '(("Doe" "John")
("Flintstone" "Fred")
("Doe" "Jane")
("Flintstone" "Wilma"))
#'name-lessp)
That is, if I didn't make an error. I didn't bother to test this.
It should also work to do:
(defun name-sort (names)
(stable-sort (sort names #'string-lessp :key #'second)
#'string-lessp
:key #'first))
(name-sort '(("Doe" "John")
("Flintstone" "Fred")
("Doe" "Jane")
("Flintstone" "Wilma")))
though it's probably less efficient. (I didn't check the algorithmic
efficiency. I'm just guessing.)