# Sorting strings containing numbers, so that "A2" \< "A10"?

**URL:** <https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372>\
**Category:** General Usage\
**Tags:** strings, sort\
**Created:** [August 14, 2017, 9:37am UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372 "2017-08-14T09:37:27Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [August 14, 2017, 9:37am UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/1 "2017-08-14T09:37:27Z")

</div>

I need to sort strings containing numbers. Is there a simple way to sort them, such that, for example, `"A2" < "A10"`? That is, I want a lexicographic compare, such that numbers in the string are compared by value.

I guess this should be a version compare. Is it implemented in Julia, maybe in a package?

---

<div class="post-metadata">

**Author:** ![klacru](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klacru/32/27890_2.png) [@klacru](https://discourse.julialang.org/u/klacru)\
**Post date:** [August 14, 2017, 10:21am UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/2 "2017-08-14T10:21:59Z")

</div>

You could try it along this way:

```julia
julia> list(s::AbstractString) = zip(split(s, r"[\d]+"), parse.(split(s, r"[^\d]+")))
list (generic function with 1 method)
julia> lex2(s::AbstractString) = map(x -> x[2] == nothing ? x[1] : x[2], list(s))
lex2 (generic function with 1 method)
julia> islesscustom(a,b) = begin
             for x in (zip(lex2(a), lex2(b)))
                 x[1] < x[2] && return true
             end;
             false
          end
islesscustom (generic function with 1 method)
julia> islesscustom("A20", "A3")
false

julia> islesscustom("A3", "A20")
true

```

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [August 14, 2017, 12:33pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/3 "2017-08-14T12:33:09Z")

</div>

Depending on the flexibility needed, here is another method that is a bit faster:

```julia
function custom_cmp(x::String)
   number_idx = findfirst(isdigit, x)
   str, num = SubString(x, 1, number_idx-1), SubString(x, number_idx, length(x))
   return str, parse(Int, num)
end

l = ["A5", "A10", "A200", "A20"]

sort(l, by = custom_cmp)

```

```julia
@btime sort(l, lt = islesscustom)
  405.706 μs (577 allocations: 25.81 KiB)

@btime sort(l, by = custom_cmp)
  2.292 μs (33 allocations: 1.31 KiB)

```

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [August 14, 2017, 1:11pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/4 "2017-08-14T13:11:26Z")

</div>

What if there are multiple numbers, “A10B3cd”? Ideally we should have a lexicographic comparison, that detects al the numbers and compares them by value.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [August 14, 2017, 1:23pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/5 "2017-08-14T13:23:40Z")

</div>

As I implied, you need to more clearly define exactly what you expect to put into the comparison. How should “5” vs “A” compare? How should “A53” vs “53A” etc.

---

<div class="post-metadata">

**Author:** ![pfitzseb](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pfitzseb/32/45566_2.png) [@pfitzseb](https://discourse.julialang.org/u/pfitzseb)\
**Post date:** [August 14, 2017, 1:42pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/6 "2017-08-14T13:42:12Z")

</div>

```julia
julia> function naturalsort(x::Vector{String})
           f = text -> all(isnumber, text) ? Char(parse(Int, text)) : text
           sorter = key -> join(f(c) for c in matchall(r"[0-9]+|[^0-9]+", key))
           sort(x, by=sorter)
       end
naturalsort (generic function with 1 method)

julia> l = ["A5a", "A10b", "A10a", "A200", "A20"];

julia> @btime naturalsort($l)
  10.196 μs (233 allocations: 6.67 KiB)
5-element Array{String,1}:
 "A5a" 
 "A10a"
 "A10b"
 "A20" 
 "A200"

```

with inspiration from [here](https://blog.codinghorror.com/sorting-for-humans-natural-sort-order/).

---

<div class="post-metadata">

**Author:** ![Paulo\_Jabardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/paulo_jabardo/32/3196_2.png) [@Paulo\_Jabardo](https://discourse.julialang.org/u/Paulo_Jabardo)\
**Post date:** [August 14, 2017, 2:26pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/7 "2017-08-14T14:26:04Z")

</div>

I don’t know if this will help you now, but if you are the one generating the strings, a good technique is to fill the number with zeros.

The following function is useful

```julia
numstring(x, n=3) = string(x + 10^n)[2:end]

```

With this function,

```julia
julia> x = "A" .* numstring.([rand(1:500) for i in 1:10], 5)
10-element Array{String,1}:
 "A00077"
 "A00137"
 "A00347"
 "A00050"
 "A00386"
 "A00347"
 "A00272"
 "A00178"
 "A00169"
 "A00160"

julia> sort(x)
10-element Array{String,1}:
 "A00050"
 "A00077"
 "A00137"
 "A00160"
 "A00169"
 "A00178"
 "A00272"
 "A00347"
 "A00347"
 "A00386"

```

This has the added benefit when naming files, they will appear in order in the file system.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [August 15, 2017, 7:48pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/8 "2017-08-15T19:48:45Z")

</div>

> [@Paulo\_Jabardo](#):
>
> This has the added benefit when naming files, they will appear in order in the file system.

You have a trick, but ls, e.g. ls -lv (can’t speak for Windows…) already has what you need to avoid naming like this:

-v natural sort of (version) numbers within text

---

<div class="post-metadata">

**Author:** ![Paulo\_Jabardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/paulo_jabardo/32/3196_2.png) [@Paulo\_Jabardo](https://discourse.julialang.org/u/Paulo_Jabardo)\
**Post date:** [August 16, 2017, 5:54pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/9 "2017-08-16T17:54:28Z")

</div>

I did not know that, cool. Thanks. But is still nice to left pad the numbers with zeros

Paulo

---

<div class="post-metadata">

**Author:** ![bjarthur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bjarthur/32/9638_2.png) [@bjarthur](https://discourse.julialang.org/u/bjarthur)\
**Post date:** [February 5, 2019, 6:50pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/10 "2019-02-05T18:50:17Z")

</div>

there is also [https://github.com/simonster/NaturalSort.jl](https://github.com/simonster/NaturalSort.jl), which sadly does not seem to be maintained.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [February 5, 2019, 11:19pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/11 "2019-02-05T23:19:28Z")

</div>

It’s a single 72-line function; should be easy enough to get working on 1.0 if someone has the interest. The main difficulty should be that the iteration protocol changed.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [February 6, 2019, 1:35pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/12 "2019-02-06T13:35:18Z")

</div>

> [@StefanKarpinski](#):
>
> It’s a single 72-line function; […] The main difficulty should be that the iteration protocol changed.

If it’s a trivial function then isn’t it a good reason to (update to 1.0 and) add this capability to the standard library? And if it’s a non-trivial one (a can of worms for security), an even better argument?

[http://unicode.org/reports/tr36/](http://unicode.org/reports/tr36/)

> ### 3.2 [Text Comparison](http://unicode.org/reports/tr36/#Text_Comparison) (Sorting, Searching, Matching)
> 
> The UTF-8 exploit is a special case of a general problem. Security problems may arise where a user and a system (or two systems) compare text differently. For example, this happens where text does not compare as users expect. […]
> 
> There are some other areas to watch for. Where these are overlooked, it may leave a system open to the **text comparison security problems**.
> 
> 1. Normalization is context dependent; do not assume NFC(x + y) = NFC(x) + NFC(y).
> 2. There are _ **two** _ binary Unicode orders: code point/UTF-8/UTF-32 and UTF-16 order. […]
> 3. Avoid using non-Unicode charsets where possible.[…]
> 4. When converting charsets, _never_ simply omit characters that cannot be converted; at least substitute U+FFFD (when converting to Unicode) or 0x1A (when converting to bytes) to reduce security problems. See also [[UTS22](http://unicode.org/reports/tr36/#UTS22)].
> 5. Regular expression engines use […]
> 
> Transitivity is crucial to correct functioning of sorting algorithms. Transitivity means that if a \< b and b \< c then a \< c. It means that there cannot be any cycles: a \< b \< c \< a.
> 
> **A lack of transitivity in string comparisons may cause security problems, including denial-of-service attacks**. As an example of a failure of transitivity, consider the following pseudocode:
> 
> ```julia
> int compare(a,b) {
> if (isNumber(a) && isNumber(b)) {
> return numberComparison(a,b);
> } else {
> return textComparison(a,b);
> }
> }
> 
> ```
> 
> **The code seems straightforward, but produces the following non-transitive result:**
> 
> **“12” \< “12a” \< “2” \< “12”**
> 
> For the first two comparisons, one of the values is not a number, therefore both values are compared as text. For the last two, both are numbers, and compared numerically. This breaks transitivity because a cycle is introduced.
> 
> The following pseudocode illustrates one way to repair the code, by sorting all numbers before all non-numbers:
> 
> ```julia
> int compare(a,b) {
> if (isNumber(a)) { if (isNumber(b)) {
> return numberComparison(a,b);
> } else {
> return -1; // a is less than b, since a is a number and b isn't }
> } else if (isNumber(b)) {
> return 1; // b is less than a, since b is a number and a isn't } else {
> return textComparison(a,b);
> }
> }
> 
> ```
> 
> Therefore, for complex comparisons, such as language-sensitive comparison, it is important to test for transitivity thoroughly.
> 
> ### 3.3 [Buffer Overflows](http://unicode.org/reports/tr36/#Buffer_Overflows)
> 
> Some programmers may rely on limitations that are true of ASCII or Latin-1, but fail with general Unicode text. These can cause failures such as buffer overruns if the length of text grows. In particular:
> 
> 1. Strings may expand in casing: Fluß → FLUSS → fluss. The expansion factor may change depending on the UTF as well. […]

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [February 6, 2019, 2:13pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/13 "2019-02-06T14:13:38Z")

</div>

Neither triviality nor non-triviality are good reasons to put something into in the base language.

---

<div class="post-metadata">

**Author:** ![Tero\_Frondelius](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tero_frondelius/32/7629_2.png) [@Tero\_Frondelius](https://discourse.julialang.org/u/Tero_Frondelius)\
**Post date:** [February 6, 2019, 2:53pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/14 "2019-02-06T14:53:27Z")

</div>

> [@StefanKarpinski](#):
>
> It’s a single 72-line function; should be easy enough to get working on 1.0 if someone has the interest.

[The pull request to fix the issue](https://github.com/simonster/NaturalSort.jl/pull/3) seems to exist. I didn’t test if it actually fixes the package.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [February 6, 2019, 3:17pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/15 "2019-02-06T15:17:14Z")

</div>

I’ve opened [an issue](https://github.com/simonster/NaturalSort.jl/issues/4) to move the package to the JuliaStrings org. Then it won’t be on Simon to maintain anymore.

---

<div class="post-metadata">

**Author:** ![laborg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laborg/32/5474_2.png) [@laborg](https://discourse.julialang.org/u/laborg)\
**Post date:** [February 6, 2019, 4:01pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/16 "2019-02-06T16:01:56Z")

</div>

This pull request is flawed. E.g. providing an empty strings already breaks it due to incorrect tuple decomposition of the `iterate()` result at the beginning.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [February 10, 2019, 3:59pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/17 "2019-02-10T15:59:34Z")

</div>

> [@StefanKarpinski](#):
>
> I’ve opened [an issue](https://github.com/simonster/NaturalSort.jl/issues/4) to move the package to the JuliaStrings org.

Great!

PHP is the language to beat, with natural sorting built in (and thus discoverable):  
[http://us3.php.net/manual/en/function.strnatcmp.php](http://us3.php.net/manual/en/function.strnatcmp.php)

With trivial function I meant at least it should be very discoverable, if not in the standard library, then possibly the docs should point to the relevant package.

> **[Sorting for Humans : Natural Sort Order](https://blog.codinghorror.com/sorting-for-humans-natural-sort-order/)**
>
> The default sort functions in almost every programming language are poorly suited for human consumption. What do I mean by that? Well, consider the difference between sorting filenames in Windows explorer, and sorting those very same filenames via...

> The default sort functions in almost every programming language are **poorly suited for human consumption**.

Most languages including made for text processing Perl and Python only have in libraries:

> <https://stackoverflow.com/questions/4836710/is-there-a-built-in-function-for-string-natural-sort>

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [February 10, 2019, 4:27pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/18 "2019-02-10T16:27:10Z")

</div>

> [@Palli](#):
>
> PHP is the language to beat

Let’s not get carried away. “Natural sorting” is a nice feature that belongs in a package, like the zillion other specialized functions. It is rather trivial to implement, and has nothing to do with comparing _languages_.

Incidentally, while I like to read Atwood’s essays, it is apparent that his thinking is biased by his (excellent) work on user interfaces. This kind of sorting may be useful when displaying strings to users, but is not universally preferable to other sorting orders. Eg when comparing keys in a sorted lookup table (`Base.searchsortedfirst`), the actual order may be irrelevant, I just want it to be fast. Arguing that those who don’t prefer this comparison function to others are not “sane” is just needless hyperbole.

---

<div class="post-metadata">

**Author:** ![jandehaan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jandehaan/32/6805_2.png) [@jandehaan](https://discourse.julialang.org/u/jandehaan)\
**Post date:** [February 10, 2019, 6:34pm UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/19 "2019-02-10T18:34:42Z")

</div>

To whom it may concern: for your consideration.

```julia
function natural(x, y)
    k(x) = [occursin(r"\d+", s) ? parse(Int, s) : s 
            for s in split(replace(x, r"\d+" => s->" $s "))]
    A = k(x); B= k(y)    
    for (a, b) in zip(A, B)
        if !isequal(a, b)
            return typeof(a) <: typeof(b) ? isless(a, b) :
                   isa(a,Int) ? true : false
        end
    end
    return length(A) < length(B)
end

```

```julia
julia> sort(["a1", "a2", "a10"])
3-element Array{String,1}:
 "a1"
 "a10"
 "a2"

julia> sort(["a1", "a2", "a10"], lt=natural)
3-element Array{String,1}:
 "a1"
 "a2"
 "a10"

```

---

<div class="post-metadata">

**Author:** ![evad](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/evad/32/15756_2.png) [@evad](https://discourse.julialang.org/u/evad)\
**Post date:** [July 11, 2020, 7:11am UTC](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372/20 "2020-07-11T07:11:26Z")

</div>

Tried out, worked like magic.  
Can you explain what does `A = k(x)` mean here?

[Next page](https://discourse.julialang.org/t/sorting-strings-containing-numbers-so-that-a2-a10/5372.md?page=2)