Skip to content

Instantly share code, notes, and snippets.

Last active May 26, 2022 21:18
Show Gist options
  • Save ericnormand/0efb967277eed772f2a0dda801927375 to your computer and use it in GitHub Desktop.
Save ericnormand/0efb967277eed772f2a0dda801927375 to your computer and use it in GitHub Desktop.
466 Eric Normand Newsletter

Custom sort order

The sort function sorts a collection based on its "natural ordering." sort-by allows you to sort a collection based on the natural ordering of the result of some function applied to the elements. Your task is to write a function sort-with which takes a sequence of elements that define the sort order.


           ; define ordering               ; collection to sort
(sort-with [:breakfast :lunch :dinner]     #{:lunch :breakfast :dinner}) ;=> (:breakfast :lunch :dinner)
(sort-with [2 3 4 :jack :queen :king :ace] [4 2 4 :king 2]) ;=> [2 2 4 4 :king]

Thanks to this site for the problem idea, where it is rated Expert in PHP. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe:

Copy link

The complexity of this code is linear with the size of the collection to sort:

(defn sort-with [order coll]
  (for [k order
        x coll :when (= k x)]

Elements in coll that don't exist in order are excluded from the sorted result.

Copy link

Here is my solution with mapped indices (Clojure beginner):

(defn sort-with [order-seq coll]
  (let [item->index (into {} (map-indexed #(vector %2 %1) order-seq))]
    (->> coll
         (map #(vector (item->index %) %))
         (sort-by first compare)
         (map second))))

Elements that are not in order-seq will appear at the beginning of the sorted result, since their index will be nil.
@jonasseglare s solution seems much more efficient and elegant though, would have never occurred to me!

Copy link

dfuenzalida commented Apr 29, 2022

Using the built-in sort-by function. Elements not in the ordered sequence will show in the beginning of the result:

(defn sort-with [oxs ys]
  (let [keyfn (zipmap oxs (range))]
    (sort-by keyfn ys)))

  (sort-with [:breakfast :lunch :dinner] #{:lunch :breakfast :dinner})
  ;; => (:breakfast :lunch :dinner)

  (sort-with [2 3 4 :jack :queen :king :ace] [4 2 4 :king 2])
  ;; => (2 2 4 4 :king)

  (sort-with [:red :orange :yellow :green :blue :indigo :violet] [:blue 1 2 :red])
  ;; => (1 2 :red :blue)

Copy link

A minor variant of @dfuenzalida's answer that keeps only the ordered elements in the result:

(defn sort-with [order xs]
  (let [m (zipmap order (range))]
    (sort-by m (filter m xs))))

Copy link

bnii commented Apr 29, 2022

(defn sort-with [order xs]
  (let [order-map (into {} (map-indexed (fn [idx v] [v idx]) order))]
    (sort-by order-map xs)))

Copy link

miner commented Apr 29, 2022

(defn sort-with [ordering coll]
  (transduce identity
             (fn ([res x] (assoc! res x (count res)))
                 ([res] (sort-by res coll)))
             (transient {})

Copy link

miner commented Apr 29, 2022

Here's a more conventional version of the same idea without transducers.

(defn sort-with [ordering coll]
  (sort-by (reduce (fn [res x] (assoc! res x (count res))) (transient {}) ordering) coll))

Copy link

The original problem asks for the unmatched elements to be appended to the result, in natural sort order. Just for fun, I came up with a solution for this variant:

(defn sort-with-original [order xs]
  (let [m (zipmap order (range))]
    (sort-by #(if-let [i (m %)]
                [nil %])
(apply str (sort-with-original "edc" "abcdefzyx"))   ; => "edcabfxyz"

Copy link

jumarko commented May 12, 2022

(defn sort-with
  "Sort `xs` according to the order defined by `template`.
  See for full instructions.

   Note: the original exercise suggests that if the character isn't in the template,
  then sort it alphabetically - Eric doesn't mention this because he tries to make it work on more generic items.
  Thus we don't implement this requirement either."
  [template xs]
  ;; I'd like to use sort-by and just found proper 'key-fn'
  ;; So I think it could be something that returns an index of the element in the template?
  (sort-by (fn [item] (.indexOf (vec template) item))

Copy link

(defn sort-with [order xs]
  (sort-by (->> order (into {} (map-indexed (fn [i x] [x i]))))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment