What’s the problem?
When a programmer is given the task of sorting file names in a list, it might be tempting to sort using something like
std::sort(). The problem with that is:
std::sort() sorts alphabetically. Suppose we have a list of file like this:
1 2 3 4 5 6 7 8 chapter1.txt chapter10.txt chapter2.txt chapter3p1.txt chapter3p2.txt chapter3p10.txt chapter11.txt chapter20.txt
If we sort it alphabetically, aka, using
1 2 3 4 5 6 7 8 chapter1.txt chapter10.txt chapter11.txt chapter2.txt # we expect chapter 2 to be in front of chapter10 chapter20.txt chapter3p1.txt chapter3p10.txt chapter3p2.txt
We see that
chapter11 have been placed before
chapter2. This make sense for an alphabetically sorted list. Both
11 is smaller than
2 since the first digit
1 is smaller than
2. However, it does not follow our intuition. As a human, we expect
2 to be bigger than
10, not the other way around.
This is where the algorithm of natural sort (sometimes called alphanumerical sort) comes in handy.
Natural sort order is an ordering of strings in alphabetical order, except that multi-digit numbers are treated atomically, i.e., as if they were a single character. Natural sort order has been promoted as being more human-friendly (“natural”) than the machine-oriented pure alphabetical order.
Pseudo-code for natural sort:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 # Preprocessing For every file name in list: processedName =  Scan for every character c in file name: If consecutive digits are found: Merge consecutive numerical characters into a single number processedName.Append(number) Else: # non-numerical character processedName.Append(c) list[current] = processedName # use the new name as name for comparison Sort list: Comparing file name x and y: For every cooresponding [xi in x] and [yi in y]: If xi == yi: Continue If both xi and yi are numbers: If xi < yi: x is smaller Else: y is smaller Else If both xi and yi are strings: If xi < yi: x is smaller Else: y is smaller Else: # One of xi or yi is a number and the other is string If xi is number: x is smaller Else: y is smaller # the list is now sorted naturally (or alphanumerically)!
After applying the algorithm, the list should look like this:
1 2 3 4 5 6 7 8 chapter1.txt chapter2.txt chapter3p1.txt chapter3p2.txt chapter3p10.txt chapter10.txt chapter11.txt chapter20.txt
The number rigit after
chapter is sorted correctly as well as the second number after
This blog only described a simplified version of natural sort. Some file manager might ignore leading and trailing spaces when sorting. Multiple consecutive spaces might be considered as one single space as well. However the overall algorithm did not change and all of these features are quite trivial to implement.
Checkout these resources: https://blog.codinghorror.com/sorting-for-humans-natural-sort-order/ https://rosettacode.org/wiki/Natural_sorting