Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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.

Example

           ; 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: https://ericnormand.me/newsletter

@jonasseglare
Copy link

jonasseglare commented Apr 28, 2022

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)]
    x))

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

@formsandlines
Copy link

formsandlines commented Apr 29, 2022

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!

@dfuenzalida
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)))

(comment
  
  (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)
  
  )

@steffan-westcott
Copy link

steffan-westcott commented Apr 29, 2022

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))))

@bnii
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)))

@miner
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 {})
             ordering))

@miner
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))

@steffan-westcott
Copy link

steffan-westcott commented Apr 29, 2022

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 %)]
                [i]
                [nil %])
             xs)))
(apply str (sort-with-original "edc" "abcdefzyx"))   ; => "edcabfxyz"

@jumarko
Copy link

jumarko commented May 12, 2022

(defn sort-with
  "Sort `xs` according to the order defined by `template`.
  See https://edabit.com/challenge/5cefoardyvgEb52JB 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))
           xs))

@KingCode
Copy link

KingCode commented May 26, 2022

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

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