Sorting Strings containing Numbers
March 24th, 2008
It’s often necessary to sort lists. The Sort method of ArrayList class shows that it can’t be difficult. Also some other classes can be sorted unless they are type IComparable.
The sort method of ArrayList class has several overloads, some can be given to a Comparer, which implements the IComparer interface.
The interface has just one method called Compare which returns equal, greater or smaller depending on the two values it compares.
If you’d make your own comparer you’d simply do that like this:
public class MySpecialComparer : object, System.Collections.IComparer { /// <summary> /// Default constructor - initializes all fields to default values /// </summary> public MySpecialComparer() { } }
There’s also a difference in ascending and descending sort order. Mention the following code which compares String descending:
public class DescendingComparer : IComparer { public int Compare(object objA, object objB) { return String.Compare(objB.ToString(), objA.ToString()); } }
The trick is just to compare B to A and not the way round.
To sort a simplest one dimensional array in alphabetical order, we’ll leverage the static “Sort” method in the Array class to sort the array. The Array.Sort method will sort the array in place, meaning we don’t have to create another array to contain the resulting array. Here is how:
String[] myAnimals = {"Zebra","Elephant","Snake"}; Array.Sort(myAnimals);
As expected this will result in the array getting sorted in the ascending order i.e. iterating the elements of this array will cause the output in the following manner:
Elephant, Snake, Zebra
Computer string sorting algorithms generally don’t order strings containing numbers in the same way that a human would do. Consider:
rfc1.txt, rfc2086.txt, rfc822.txt
It would be more friendly if the program listed the files as
rfc1.txt, rfc822.txt, rfc2086.txt
Filenames sort properly if people insert leading zeros, but they don’t always do that.
It’s kinda tricky when strings that contain numbers are sorted ’cause they’ve to be sorted numerically.
Imagine an array of values like this:
string[] Items = { "z4", "z2", "z15", "z1" };
The idea is to write a Comparer (implements IComparer) which extracts the numeric part e.g. by RegEx: [0-9]*
Then sort as already familiar with a Collections.Sort method that uses the comparator.
Generally you’d “invent” an algorithm that breaks strings into chunks, where a chunk contains either all alphabetic characters, or all numeric characters. These chunks are then compared against each other. If both chunks contain numbers, a numerical comparison is used. If either chunk contains characters, the ASCII comparison is used.
Ian Griffith offered a code sample that helps to handle string sorting with numbers:
/// <summary> /// Compares two sequences. /// </summary> /// <typeparam name="T">Type of item in the sequences.</typeparam> /// <remarks> /// Compares elements from the two input sequences in turn. If we /// run out of list before finding unequal elements, then the shorter /// list is deemed to be the lesser list. /// </remarks> public class EnumerableComparer<T> : IComparer<IEnumerable<T>> { /// <summary> /// Create a sequence comparer using the default comparer for T. /// </summary> public EnumerableComparer() { comp = Comparer<T>.Default; } /// <summary> /// Create a sequence comparer, using the specified item comparer /// for T. /// </summary> /// <param name="comparer">Comparer for comparing each pair of /// items from the sequences.</param> public EnumerableComparer(IComparer<T> comparer) { comp = comparer; } /// <summary> /// Object used for comparing each element. /// </summary> private IComparer<T> comp; /// <summary> /// Compare two sequences of T. /// </summary> /// <param name="x">First sequence.</param> /// <param name="y">Second sequence.</param> public int Compare(IEnumerable<T> x, IEnumerable<T> y) { using (IEnumerator<T> leftIt = x.GetEnumerator()) using (IEnumerator<T> rightIt = y.GetEnumerator()) { while (true) { bool left = leftIt.MoveNext(); bool right = rightIt.MoveNext(); if (!(left || right)) return 0; if (!left) return -1; if (!right) return 1; int itemResult = comp.Compare(leftIt.Current, rightIt.Current); if (itemResult != 0) return itemResult; } } } }
When using it a regular expression for the numbers is needed.
Using C# 3.0 it can be used that way:
Func<string, object> convert = str => { try { return int.Parse(str); } catch { return str; } }; var sorted = testItems.OrderBy( str => Regex.Split(str.Replace(" ", ""), "([0-9]+)").Select(convert), new EnumerableComparer<object>());
Again the lambda expression can help a lot. sorted is an untyped listed that can be iterated with foreach.
When sorting / comparing strings that contain numbers you always should consider to sort them the way a human would do.
