How to implement a natural sort algorithm in c++?

663

+6 Q:

I'm sorting strings that are comprised of text and numbers. I want the sort to sort the number parts as numbers, not alphanumeric.

For example I want: abc1def, ..., abc9def, abc10def

instead of: abc10def, abc1def, ..., abc9def

Does anyone know an algorithm for this (in particular in c++)

Thanks

+6 A:

This is known as natural sorting. There's an algorithm here that looks promising.

Be careful of problems with non-ASCII characters (see Jeff's blog entry on the subject).

Dominic Rodger 2009-03-13 11:18:54

Thats sweet but I don't have acces to boost :-|

Will 2009-03-13 11:35:54

Then it looks like Paul Tomblin's answer may be more helpful to you - the C++ variant doesn't seem to use anything funky.

Dominic Rodger 2009-03-13 11:39:50

+4 A:

I asked this exact question (although in Java) and got pointed to http://www.davekoelle.com/alphanum.html which has an algorithm and implementations of it in many languages.

Paul Tomblin 2009-03-13 11:31:41

+1 Thanks Paul - I looked for natural sort and the C++ tag, but didn't find anything.

Dominic Rodger 2009-03-13 11:40:27

ansaurus