Sorting lists in Clojure

Question

I'm trying to sort a Clojure list (or seq, if that's what it's called) in a specific way. I would like it sorted in the priority of last item in decending order, then first item in ascending order. An example:

(def pnts '((1 2)
            (2 4)
            (3 2)
            (4 10)
            (5 3)
            (6 1)
            (7 2)))

(sort-by last > pnts)
;; ((4 10) (2 4) (5 3) (1 2) (3 2) (7 2) (6 1))
;; Notice how (1 2), (3 2), (7 2) are sorted. This
;; is correct and is what I want.

The (sort-by last) seems to be doing the trick, although this might be because the points are initially sorted by the first item. The way I am implementing the ASCII/CLI graphing script that I am writing the points will always be ordered like pnts was. My question is what is a command that can guarantee such a sorting preference?

PS I tried doing (sort-by (juxt last first) (juxt > <) pnts) but to no avail.

DaoWen · Accepted Answer · 2014-01-21 06:46:25Z

9

I think you were on the right track using juxt. Assuming that your points are all numbers, you can just compose last and - to emulate a descending natural order on the last component.

user=> (sort-by (juxt (comp - last) first) (shuffle pnts))
((4 10) (2 4) (5 3) (1 2) (3 2) (7 2) (6 1))

edited Jan 21, 2014 at 6:46

answered Jan 20, 2014 at 19:47

DaoWen

33.1k6 gold badges77 silver badges102 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user2958652 Over a year ago

I am not too familiar with comp nor with juxt -- would this sort the nodes last descending then the first ascending? Your example shows it as so, but I want to be certain it will (I can't see what this example is doing).

user2958652 Over a year ago

Never mind noisesmith answered in the other question. Thanks to both, and thanks to noisesmith for the honesty :) I will be researching further into both juxt and comp.

A. Webb · Accepted Answer · 2014-01-20 19:57:08Z

7

Sort uses Java's sort, which is stable, so you can also just sort twice

 (def pnts (shuffle '((1 2) (2 4) (3 2) (4 10) (5 3) (6 1) (7 2))))

 (->> pnts (sort-by first <) (sort-by last >))
 ;=> ((4 10) (2 4) (5 3) (1 2) (3 2) (7 2) (6 1))

answered Jan 20, 2014 at 19:57

A. Webb

26.5k1 gold badge67 silver badges97 bronze badges

Comments

noisesmith · Accepted Answer · 2014-01-20 19:36:20Z

3

I have shuffled the input to ensure that the result is stable for arbitrary input order:

(sort  #(or (> (last %1) (last %2))
             (and (= (last %1) (last %2))
                  (< (first %1) (first %2))))
       (shuffle '((1 2) (2 4) (3 2) (4 10) (5 3) (6 1) (7 2))))
=> ((4 10) (2 4) (5 3) (1 2) (3 2) (7 2) (6 1))

Here we verify, even with 1000 reorderings of the input, there is only one ordering of the output:

(count (into #{}
             (repeatedly
              1000
              (fn [] (sort #(or (> (last %1) (last %2))
                                (and (= (last %1) (last %2))
                                     (< (first %1) (first %2))))
                           (shuffle '((1 2) (2 4) (3 2) (4 10) (5 3) (6 1) (7 2))))))))
=> 1

Here we show that shuffle produces a large variety of orderings:

(count (into #{}
             (repeatedly
              1000
              (fn [] (shuffle '((1 2) (2 4) (3 2) (4 10) (5 3) (6 1) (7 2)))))))
=> 899

(of course since shuffle is randomized the results will vary, but the count seems to be typically in the 850 - 950 range)

answered Jan 20, 2014 at 19:36

noisesmith

20.2k2 gold badges43 silver badges50 bronze badges

9 Comments

user2958652 Over a year ago

Ahh nice. Clojure Docs clojuredocs.org/clojure_core/clojure.core/sort recommended to use sort-by when I need to access the first/last item; I assume then that sort-by is a macro for keywords n' such.

noisesmith Over a year ago

DaoWen's answer below actually solves this much more elegantly, and should probably be accepted as the best answer here.

user2958652 Over a year ago

Really? I am a Clojure beginner, and I thought that DaoWen's answer looked a bit hackish. Would his method be just as fast?

noisesmith Over a year ago

Definitely at least as fast, maybe faster. The conciseness is actually a bonus once you know the language better. It works because (comp - last) gives you a reverse order of last, and if you sort two element lists, the algorithm works by sorting by first element, then the next if the first are equivalent. So it is automatically doing what I painstakingly do by hand.

A. Webb Over a year ago

Sorting twice should be on par too (not tested). Doing two things n log n times should be about the same as doing n log n things twice.

|

Collectives™ on Stack Overflow

Sorting lists in Clojure

3 Answers 3

2 Comments

Comments

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related