How to sort alphabetically but respecting groups or symbols?

Question

What I would like to do is to sort a list of textual identifiers (think of a file name for example). The sorting algorithm I'm looking for is a kind of alphabetic sorting, but taking groups into account.

For example, sorting "D1" to "D21" should be:

D1, D2, D3, ..., D21

And not:

D1, D10, D11, D12, ... D2, D20, D21, D3, ...

I've been a lot of time trying to accomplish such way of sorting but still can't find how to do it. The bigger the group the harder it seems.

Is there anyone that could guide me through or give me some pseudo code or code in any language?

Thanks.

gnarf · Accepted Answer · 2009-09-09T00:33:02.753

3

Detect the position the strings differ first.
If both values at that position are numbers:
- read forward, one character at at time, until you find a non-number in either string.
- If only one string is non-numeric, it is "smaller"
- If Both strings are non-numeric at the same point, compare numbers at the earlier detected position
Otherwise
- compare alphabetically the letters at the position

edited Sep 09 '09 at 00:33

answered Sep 09 '09 at 00:25

gnarf

105,192
25
127
161

Thanks! That easy and I've spent a lot of time trying to make it. – Shantia Sep 09 '09 at 00:30
Updated it to be a little lighter on memory usage, there is no need to store or capture. – gnarf Sep 09 '09 at 00:34

score 2 · Answer 2 · edited Oct 21 '18 at 03:34

2

Jeff has a post on this with links to several implementations. It appears to be called "natural sorting".

See also this question.

edited Oct 21 '18 at 03:34

Cœur

37,241
25
195
267

answered Sep 09 '09 at 00:42

John Fouhy

41,203
19
62
77

score 1 · Answer 3 · answered Sep 09 '09 at 00:25

1

The Unix sort utility has a 'numeric sort' option -n which sorts the way you want, rather than a plain dictionary sort.

Maybe look for information about 'numeric sort'

The Unix source code of sort will be available, but probably difficult to follow.

answered Sep 09 '09 at 00:25

pavium

14,808
4
33
50

score 1 · Answer 4 · answered Sep 09 '09 at 00:55

PHP: the nat*sort family of functions (natsort, natcasesort, ...)

Perl:

sub natcmp {
    # from http://www.perlmonks.org/?node_id=540890
    my @a = split /(\d+)/, (shift or $a);
    my @b = split /(\d+)/, (shift or $b);

    my $last = min(scalar @a, scalar @b)-1;
    my $cmp;
    for my $i (0 .. $last) {
        unless($i & 1) {  # even
            $cmp = lc $a[$i] cmp lc $b[$i] || $a[$i] cmp $b[$i] and return $cmp;
        } else {  # odd
            $cmp = $a[$i] <=> $b[$i] and return $cmp;
        }
    }
    return scalar @a <=> scalar @b;  # shortest array comes first
}

# ...

@sorted_array = sort natcmp @array;

What you're looking for is called a natural sort.

score 1 · Answer 5 · answered Sep 09 '09 at 01:01

Others have pointed out that it's called "natural sort". For code, this Python implementation is the simplest I've found. It basically uses a regex to split each string into heterogeneous lists of ints or strings, and then compares those.

This takes advantage of a couple of Python features w.r.t. object comparison. First, that you can compare ints and strings directly (ints sort as less-than any string). Second, that you can compare heterogeneous lists (it compares elements from the beginning until it finds a difference).

How to sort alphabetically but respecting groups or symbols?

5 Answers5