Alphabetical/Natural sorting in Clojure/Clojurescript

natural-sort.clj

(ns util.natural-sorting
  (:refer-clojure :exclude [sort sort-by])
  (:require [clojure.string]))

(defn parse-int [s]
  #?(:clj (Long/parseLong s)
     :cljs (js/parseInt s)))

(defn vector-compare [[value1 & rest1] [value2 & rest2]]
  (let [result (compare value1 value2)]
    (cond
      (not (zero? result)) result
      (nil? value1) 0
      :else (recur rest1 rest2))))

(defn prepare-string [s]
  (let [s (or s "")
        parts (vec (clojure.string/split s #"\d+"))
        numbers (->> (re-seq #"\d+" s)
                     (map parse-int)
                     (vec))]
    (vec (interleave (conj parts "") (conj numbers -1)))))

(defn natural-compare [a b]
  (vector-compare (prepare-string a)
                  (prepare-string b)))

(defn sort [coll] (clojure.core/sort natural-compare coll))

(defn sort-by [keyfn coll]
  (clojure.core/sort-by keyfn natural-compare coll))

It breaks for (sort ["C" "C4.1a"])

Issues:

1. interleave drops items from the longest argument
2. Instead of splitting and matching on \d+ and then combining the result, maybe it makes sense to use (clojure.string/split s #"(?<=[^\d])(?=\d)|(?<=\d)(?=[^\d])") and then just convert every other item to str (odd or even depends on whether the first one can be converted).

@rodsenra Change last part of line 22 to (conj numbers 0) and (sort ["C" "C4.1a"]) will work.

@p-himik For #1, it's okay that interleave drops items from longer argument, we'll reach a final "" or 0 on the shorter one (after making the change I mentioned above) and will be done comparing. For #2, regex101.com shows more than twice as many steps to evaluate your more complicated regex vs. using the simpler \d+. Some actual performance testing might be warranted?

A version of vector comparison with lazy seqs instead of loop/recur:

(defn- vector-compare [a b]
  (or (first (drop-while zero? (map compare (conj a nil) (conj b nil)))) 0))

@wevrem thanks, snippet fixed with (conj numbers 0)

@wilkerlucio In further testing, we should conj -1, not 0, to the list of numbers, otherwise (sort ["0" ""]) will fail.

If anyone wants some tests I wrote a series:

(ns tove.natural-sort-test
  (:require
   [clojure.test      :refer [deftest is]]
   [tove.natural-sort :as nsort]))

(deftest parse-int
  (is (= (nsort/parse-int "1")
         1)))

(deftest vector-compare
  (is (= (nsort/vector-compare ["1"] ["2"])
         -1))
  (is (= (nsort/vector-compare ["1"] ["1"])
         0))
  (is (= (nsort/vector-compare ["2"] ["1"])
         1))

  (is (= (nsort/vector-compare ["1" "1"] ["2" "2"])
         -1))
  (is (= (nsort/vector-compare ["1" "1"] ["1" "1"])
         0))
  (is (= (nsort/vector-compare ["2" "2"] ["1" "1"])
         1))
  (is (= (nsort/vector-compare ["2" "1"] ["2" "2"])
         -1))
  (is (= (nsort/vector-compare ["2" "1"] ["1" "2"])
         1))

  (is (= (nsort/vector-compare [1] [2])
         -1))
  (is (= (nsort/vector-compare [1] [1])
         0))
  (is (= (nsort/vector-compare [2] [1])
         1))

  (is (= (nsort/vector-compare "1" "2")
         -1))
  (is (= (nsort/vector-compare "1" "1")
         0))
  (is (= (nsort/vector-compare "2" "1")
         1))

  (is (= (nsort/vector-compare "10" "11")
         -1))
  (is (= (nsort/vector-compare "10" "10")
         0))
  (is (= (nsort/vector-compare "11" "10")
         1))

  ;; Only ever looks at the first element in the sequence and returns if there is a difference.
  ;; So for a character sequence it only cares about the first character.
  (is (= (nsort/vector-compare "9" "10")
         8))
  (is (= (nsort/vector-compare "90" "10")
         8))
  (is (= (nsort/vector-compare "95" "15")
         8))
  (is (= (nsort/vector-compare "90" "19")
         8))

  ;; But if we give it a sequence of actual numbers it will of course compare the entire numbers, in turn.
  (is (= (nsort/vector-compare [90] [19])
         1))
  (is (= (nsort/vector-compare [20] [19])
         1))
  (is (= (nsort/vector-compare [19] [19])
         0))
  (is (= (nsort/vector-compare [19 1] [19 1])
         0))
  (is (= (nsort/vector-compare [19 2] [19 1])
         1))
  (is (= (nsort/vector-compare [18] [19])
         -1)))

(deftest natural-compare
  (is (= (nsort/natural-compare "hest1" "hest2")
         -1))
  (is (= (nsort/natural-compare "hest1" "hest1")
         0))
  (is (= (nsort/natural-compare "hest1" "hest1")
         0))

  (is (= (nsort/natural-compare "Märrklobb 1" "Märrklobb 5")
         -1))
  (is (= (nsort/natural-compare "Märrklobb 1" "Märrklobb 1")
         0))
  (is (= (nsort/natural-compare "Märrklobb 2" "Märrklobb 1")
         1))

  ;; Since natural-compare splits strings at integers and puts them into the sequence it will
  ;; compare the words and the numbers separately.
  (is (= (nsort/natural-compare "Märrklobb 20" "Märrklobb 1")
         1))
  (is (= (nsort/natural-compare "Märrklobb 20" "Märrklobb 3") ; So this actually works!
         1))
  (is (= (nsort/natural-compare "Märrklobb 20" "Märrklobb 30")
         -1)))


(deftest sort
  (let [märrklobbs (for [i (range 1 13)] (str "Märrklobb " i))]
    (is (= (nsort/sort (shuffle märrklobbs))
           märrklobbs)))
  (is (= (nsort/sort ["0" "" "Gris"])
         '("" "0" "Gris"))))

Cool! Thanks! I'm going to use this for at least one open-source project. I hope that's OK. Gists, including this one, don't typically include open-source licenses.

FWIW, I ended up with this version. On my benchmarks, it was faster by around 30-50%.

(defn prepare-string
  "Splits the string `s` into a vector of alternating
  numbers-strings where the first item is always a string,
  potentially empty."
  [s]
  (when (seq s)
    (let [parts (vec (re-seq #"\d+|\D+" s))
          first-number? (re-matches #"\d" (subs (nth parts 0) 0 1))]
      (if first-number?
        (into [""]
              (map-indexed (fn [idx part]
                             (cond-> part (even? idx) (parse-long))))
              parts)
        (into []
              (map-indexed (fn [idx part]
                             (cond-> part (odd? idx) (parse-long))))
              parts)))))

It's probably too small to warrant it, but I created a repository (four years ago) so I could pull this into my other projects:

https://github.com/wevre/natural-compare

Thanks for the updates @p-himik and @wevre!

Since your repo has a license, @wevre, I'll probably just use it!
I'm just using it in babashka scripts at the moment, so performance is not a concern.

I suppose a limitation is that the number segments cannot exceed max long.
This is not a concern for my current usage.

Raised an issue here: wevre/natural-compare#4 happy to help if you'd like to address.

hi folks, about license, feel free to use, no restrictions

Even though I told Lee I wasn't going to, I wrote a new implementation that handles integer overflow.

I'm not using str/split or mapv parse-int so I have a hunch that it is more lazy and more performant especially on long strings where the sort order can be determined early on without needing to split the entire string. It's just a hunch though. Anyone interested in doing some profiling? I'll get to it eventually...

Ha! That's awesome @wevre! I've no real interest in performance at this point, but maybe @p-himik has an interest?

I am indeed curious enough to profile it myself and also publish some generative tests I have already written for it in my own code. Just don't have enough time at the moment. Will probably get to it some time next week.

I did some benchmarking (rudimentary) and updated my library to version 0.0.10. Short story is the "lazy" version does outperform implementations based on splitting and parsing, but only for long (for some definition of long) strings, which I think are more rare. At least in situations where I use and where I imagine having a need to use natural sorting, I think they would be rare. Same goes for overflow, it's not a situation I am concerned with. Maybe my situation is an outlier, but so far I've had more control over the types of strings I'm needing to sort.

In this version 0.0.10 of my library I included implementations and tests for my original parse version (which remains the default), my lazy version, a bigint-based version (suggested by Lee), Wilker's original, and Eugene's version. I hope that is okay, I think I have explicit okay from everyone except Eugene but I'm guessing he is okay with including his version.

Sure, I don't mind.