Sunday 29 September 2013

Natural Sort Order

Ten Before Two But 10 After 2

A recent update to our flagship product takes advantage of the server-side paging capabilities of the DevExpress Grid control. Naturally, this change has involved the migration of much client-side C# code into server-side table changes, triggers, and stored procedures, all written in SQL. One of the casualties was a particularly hirsute C# method which used to sort table contents into what's sometimes called "Natural Order", so that e.g. DC10 would come after DC9, rather than the naive collation or ASCII order, which would have them reversed.

For reasons unknown it fell to me to implement our Natural Sort. Easy I thought, I'll ask Google for the answer. That's when I discovered there's really no such thing as The Natutral Sort Order. It depends on your particular data, and your specific requirements, to a frankly surprising degree. Of course, there is plenty of material to choose from on the web. Jeff Atwood's Coding Horror on the subject is quite a good central station for your exploration of the matter. But this plenitude is also a bit of a problem. After an hour or two of research, I'd decided my best plan was to design and implement my own, newly reinvented wheel.

Fields

The basic approach is to partition or "stripe" the input (unsorted) data into a sequence of fields, alternating alphabetical content with numerical, and then treat each field as its own Sort By column - sorting the alpha fields as normal, and the numeric fields numerically. In the above DC9 / DC10 example, this results in an initial alpha field containing "DC" in both cases, followed by a numeric field containing the integers 9 and 10, which are then subjected to a numerical sort.

Some of the examples I'd read performed this latter sort by actually converting the input data field into an integer, then using the language's numeric comparison capabilities. I didn't want to use that approach, because a 32-bit signed integer can only be used for field sizes up to 9, a 64-bit one 18, and so on. I had no specification to assure me customer data wouldn't exceed such an arbitrary bound, so I fell back on the old workaround of keeping the numeric fields in string form, but left-padding them with zeros until all the rows were the same length, allowing an alpha sort to do the job of a numeric one. This is essentially part of what we do when we adopt the ANSI date format, e.g. 2013-09-29, to get correctly ranked dates.

Collations

Notice that it doesn't matter which padding character you use to right-align the numeric fields, just as long as it doesn't come after 0 (zero) in the collation order. This is important later.

One fun fact I found while researching collations was that aa comes after ab in the Danish / Norwegian collation order. For historical-typographical reasons, aa is treated (while sorting) as identical to the letter å, which just happens to be the last letter of their shared alphabet. Never mind; we'll just have to assume anyone using a particular collation order knows what they're doing, and won't be surprised by results which after all should in all cases appear perfectly non-anomalous to them.

Field Sizes

Okay, so now we have this requirement to right-justify our numeric fields by left-padding them with e.g. zeros. What fixed field size should we pad them out to? Well our input data, being stored in a traditional, relational database, has some particular maximum string length. In my case that length was 200. There's nothing to stop our customers filling every single character space with a decimal digit. So we could be looking at a numeric field of width 200.

What about the alpha fields? These don't require padding, since standard left-to-right string comparisons work fine for them. But note that every alpha character "uses up" one position in the input data, rendering that location unavailable for storing a subsequent digit. Long story short, we can stuff any alpha prefix into the left edge of our 200-character field, and still have enough room to fit and pad out the remaining, right-justified, numeric content.

For performance reasons, the ultimate destination for this calculation was a "live" Sort Order column in the relevant database table, rather than a UDF call at SQL SELECT time. That's why my buffer size had to be allocated statically, rather than optimised with reference to the worst case requirements of the data actually in the table; we didn't want a new row of data invalidating the precomputed sort orders of the old data.

Islands and Seas

You might worry about non-digit characters encroaching on the padding space of our numeric fields, and you'd be right to. Actually everything works okay as long as we stick to letters and digits. Anomalies can start to appear when we introduce punctuation characters, especially when using ASCII collation. The numeric digits and the upper- and lower-case letters can be seen to form three disconnected "islands" of codes, surrounded by four seas of punctuation characters.

In practice, these anomalies are mitigated by our customers' sparse use of such punctuation, and tendency to apply it consistently whenever it is used at all. As a further mitigation, I changed the padding character from a zero digit to a space, ensuring that padded-out numeric fields are essentially guaranteed to sort lower than any alpha or other character found in the same region.

Example

The following, correctly sorted data can be seen to illustrate these adjustments. Notice, in the Natural Sort column, the use of the space character as filler, and the fact that the 'h' of 'Coach' occupies the same character column position as the '1' of 'Van 1234' without causing any problem:

Simple Sort   Natural Sort

 Coach 12      Coach  2
 Coach 2       Coach 12
 Van 1234      Van  234
 Van 234       Van 1234

Field Count

Obviously the input data might contain further alternating fields of non-numeric and numeric data. What should we do with subsequent fields? Well, we just package them up in pairs using exactly the same algorithm as the first, and when we have done this enough times to consume all of the input, return the concatenation of all these field blocks as the sortable key.

There is another minor optimisation available here. Obviously the first field pair must have consumed at least one character from the input. This means that the field "buffer" for the second pair can be made one character shorter than the first - say, 199 characters instead of 200. Likewise, if input characters remain after the second or subsequent field pair have been extracted, then that pair must have consumed at least two characters, so the next buffer size can be 197, or 195, or 193, or...

Yes, quite. The law of diminishing returns cuts in quite promptly here, especially since we decided that a total of 3 field pairs would be more than adequate for our customers' requirements (actually there is an auto-generation element in our product, designed to nudge them into using just a single field pair: an alpha prefix, followed by a numerical index). So I just left all my buffers at width 200. You should obviously make use of this optimisation if your input size limit is much lower than 200, or if you decide to use a lot more significant field pairs.

Coding and Testing

This works adequately and was ultimately accepted for production, but I must acknowledge here the excellent work done by our Test Department, both in testing my new UDF out-of-sequence when I asked - quite unreasonably - for an early comparison with the old client-side C# function (come to think of it, how the hell did they even do that?), and also in uncovering pretty quickly all of the corner cases - punctuation, padding characters - mentioned above.

Oh, the code? Yeah sure, here ya go. Should be quite easy to hunt down the few rogue "200"s to adapt it for your use. You might also want to limit the number of iterations to prevent DOS attacks (we use only 3). As I said at the outset, it's still surprisingly specific and might not work for you. For example, it doesn't recognise decimal points / numeric separators. The truth is, there simply does not exist one Natural Sort Algorithm suitable for all data.

CREATE FUNCTION [dbo].[NaturalSort](@input NVARCHAR(200))
RETURNS NVARCHAR(MAX)
AS
BEGIN
  DECLARE
    @count INT = LEN(@input),
    @result NVARCHAR(MAX) = '',
    @p INT = 1, @q INT, @x INT, @y INT
  WHILE @p <= @count
  BEGIN
    SELECT @x = PATINDEX('%[0-9]%', SUBSTRING(@input, @p, @count) + '0') - 1
    SELECT @q = @p + @x
    SELECT @y = PATINDEX('%[^0-9]%', SUBSTRING(@input, @q, @count) + '!') - 1
    SELECT @result = @result + SUBSTRING(@input, @p, @x) +
      REPLICATE(' ', 200 - @x - @y) + SUBSTRING(@input, @q, @y)
    SELECT @p = @q + @y
  END
  RETURN @result
END

Three Onions Holding Up A Melon

Who Ordered That?

A favourite Twitter follow is @maanow, with their daily MAA Minute Math problems. These are usually simple little scenarios that take, as implied by the name, a minute or so to solve. But one of the best so far, I don't mind you knowing, took me a little longer than that. It involved three touching 1" radius spheres supporting another sphere of radius 2", and asked: what's the height of this arrangement?
http://maaminutemath.blogspot.co.uk/2013/08/august-7-2013.html
What surprises me about the solution to this one is the appearance of the square root of 69 in the answer. Doesn't that strike you as more than a little bit literally odd?

The solution is arrived at by first noticing that a line connecting the centre of the large sphere to the centre of one of the smaller, touching ones, has length 3 (all dimensions may as well be in inches; it's immaterial to the result). Now, this line is the hypotenuse of a right triangle, whose third vertex is the midpoint of an equilateral joining the centres of the three smaller spheres. This second triangle has side length 2, so the distance from its midpoint to its centre is 2/√3. Squaring both this length, and that of the earlier hypotenuse, en route to the ultimate solution, we discover that curious √69 emerging from the fact that 3³ - 2² = 23 = 69/3.

That's all, just wanted to draw your attention to this little oddity today.