Sorting a list of variable length integers delimited by decimal points...

Question

Hey guys,

I'm in need of some help.

I have a list of delimited integer values that I need to sort. An example:

Typical (alpha?) sort:

1.1.32.22

11.2.4

2.1.3.4

2.11.23.1.2

2.3.7

3.12.3.5

Correct (numerical) sort:

1.1.32.22

2.1.3.4

2.3.7

2.11.23.1.2

3.12.3.5

11.2.4

I'm having trouble figuring out how to setup the algorithm to do such a sort with n number of decimal delimiters and m number of integer fields.

Any ideas? This has to have been done before. Let me know if you need more information.

Thanks a bunch! -Daniel

Answer 1

versionsort does exactly what you're looking for.

The comparison algorithm is strverscmp, here's a description of it from the man page:

What this function does is the following. If both strings are equal, return 0. Otherwise find the position between two bytes with the property that before it both strings are equal, while directly after it there is a difference. Find the largest consecutive digit strings containing (or starting at, or ending at) this position. If one or both of these is empty, then return what strcmp() would have returned (numerical ordering of byte values). Otherwise, compare both digit strings numerically, where digit strings with one or more leading zeroes are interpreted as if they have a decimal point in front (so that in particular digit strings with more leading zeroes come before digit strings with fewer leading zeroes). Thus, the ordering is 000, 00, 01, 010, 09, 0, 1, 9, 10.

Answer 2

All you really need to do is to write "compare()" and then you can plug that into any sort algorithm.

To write compare, compare each field from left to right, and if any field is higher, return that that argument is higher. If one argument is shorter, assume that remaining fields are 0.

Answer 3

General solution is to convert this string into array of bytes, then use qsort and specify comparison function.

Answer 4

It is called natural sort. See Natural Sorting algorithm. For example, Darius Bacon's answer in Python:

def sorted_nicely(strings): 
    "Sort strings the way humans are said to expect."
    return sorted(strings, key=natural_sort_key)

def natural_sort_key(key):
    import re
    return [int(t) if t.isdigit() else t for t in re.split(r'(\d+)', key)]

Answer 5

Check out radix sort.