C# - Custom method of sorting strings

In this article you can find how to create custom method of sorting strings in C#.

For the beginning let’s create an example list of strings, which are compass directions in random order.

var directions = new List<string>()
{
    "South East",
    "North West",
    "East",
    "South West",
    "North",
    "West",
    "North East",
    "South"
};

var directions = new List<string>()

{

"South East",

"North West",

"East",

"South West",

"North",

"West",

"North East",

"South"

};

When we iterate through the collection using foreach loop and print items to the console, we should see the same order as above.

foreach (var direction in directions)
    Console.WriteLine(direction);

1 2	foreach (var direction in directions) Console.WriteLine(direction);

Indeed, the output is as expected.

South East
North West
East
South West
North
West
North East
South

South East

North West

East

South West

North

West

North East

South

Time to sort something. We can achieve it in different ways, however in this article I’d like to show two most popular.

1. List<T>.Sort();

Sort method is available against List objects and by default, in case of strings, it sorts those in alphabetical order. In the background it uses Quicksort algorithm and this implementation is considered as unstable. It means it’s not guaranteed two the same elements will preserve the same order after sorting as it was before. It may not make any difference when sorting just strings, however may be important when sorting lists of other, more complex objects.

Let’s sort our prepared list using below code. Please notice Sort function doesn’t return anything and just alters the original collection, therefore we lose the initial order.

directions.Sort();

1	directions.Sort();

After printing it to screen again, using the same loop as before we can see items in alphabetical order.

East
North
North East
North West
South
South East
South West
West

East

North

North East

North West

South

South East

South West

West

So far, so good, but now we’d like to sort the collection slightly different. Still in alphabetical order, however starting comparison from the end of each string, not the beginning as usual. To achieve it we need to implement custom algorithm, because built-in method doesn’t provide such functionality.

Again, we have a choice. When we look closer to the Sort function, we can see it’s overloaded. I’d like to focus on two options: Comparison<string> comparison and IComparer<string> comparer.

1.a. Comparison<string> comparison

Comparison is delegate type declared as you can see below, which receives two arguments of the same type (string in our case) and returns integer.

public delegate int Comparison<in T>(T x, T y);

1	public delegate int Comparison<in T>(T x, T y);

As a result of above we need to create our custom comparison method which has two string arguments and returns int. It’ll be used by sorting algorithm to compare pairs of two strings.

public static int CompareReversed(string value1, string value2)
{
    return Reverse(value1).CompareTo(Reverse(value2));
}

public static int CompareReversed(string value1, string value2)

{

return Reverse(value1).CompareTo(Reverse(value2));

}

The method uses built-in CompareTo, which returns 0 when items are equal and either -1 or 1 when items are not equal. Existence of minus depends whether value1 should be before value2 or the other way. We also need function to temporary reverse the values (e.g. abc to cba).

public static string Reverse(string value)
{
    return new string(value.ToArray().Reverse().ToArray());
}

public static string Reverse(string value)

{

return new string(value.ToArray().Reverse().ToArray());

}

This is it. Now we can replace previous call of Sort with the new one.

directions.Sort(CompareReversed);

1	directions.Sort(CompareReversed);

After above changes the output is totally different, but directions are sorted as we expected, so our custom comparison function works fine.

North
South
East
North East
South East
West
North West
South West

North

South

East

North East

South East

West

North West

South West

And full scope is here.

using System;
using System.Collections.Generic;
using System.Linq;

namespace StringSorting
{
    class Program
    {
        static void Main(string[] args)
        {
            var directions = new List<string>()
            {
                "South East",
                "North West",
                "East",
                "South West",
                "North",
                "West",
                "North East",
                "South"
            };

            directions.Sort(CompareReversed);

            foreach (var direction in directions)
                Console.WriteLine(direction);

            Console.ReadLine();
        }

        public static int CompareReversed(string value1, string value2)
        {
            return Reverse(value1).CompareTo(Reverse(value2));
        }

        public static string Reverse(string value)
        {
            return new string(value.ToArray().Reverse().ToArray());
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

namespace StringSorting

{

class Program

{

static void Main(string[] args)

{

var directions = new List<string>()

{

"South East",

"North West",

"East",

"South West",

"North",

"West",

"North East",

"South"

};

directions.Sort(CompareReversed);

foreach (var direction in directions)

Console.WriteLine(direction);

Console.ReadLine();

}

public static int CompareReversed(string value1, string value2)

{

return Reverse(value1).CompareTo(Reverse(value2));

}

public static string Reverse(string value)

{

return new string(value.ToArray().Reverse().ToArray());

}

1.b. IComparer<string> comparer

Second option is to create a class implementing IComparer<T> interface, which contains Compare method.

public int Compare (T x, T y);

1	public int Compare (T x, T y);

Let’s implement it, using the same logic as previously.

public class ReversedComparer : IComparer<string>
{
    public int Compare(string value1, string value2)
    {
        return Reverse(value1).CompareTo(Reverse(value2));
    }

    public string Reverse(string value)
    {
        return new string(value.ToArray().Reverse().ToArray());
    }
}

public class ReversedComparer : IComparer<string>

{

public int Compare(string value1, string value2)

{

return Reverse(value1).CompareTo(Reverse(value2));

}

public string Reverse(string value)

{

return new string(value.ToArray().Reverse().ToArray());

}

This time we need to pass to Sort function an instance of our ReversedComparer class.

directions.Sort(new ReversedComparer());

1	directions.Sort(new ReversedComparer());

Rebuild, run, and the output is correct again. Directions are sorted with our custom comparer.

North
South
East
North East
South East
West
North West
South West

North

South

East

North East

South East

West

North West

South West

And full scope is here.

using System;
using System.Collections.Generic;
using System.Linq;

namespace StringSorting
{
    class Program
    {
        static void Main(string[] args)
        {
            var directions = new List<string>()
            {
                "South East",
                "North West",
                "East",
                "South West",
                "North",
                "West",
                "North East",
                "South"
            };

            directions.Sort(new ReversedComparer());

            foreach (var direction in directions)
                Console.WriteLine(direction);

            Console.ReadLine();
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

namespace StringSorting

{

class Program

{

static void Main(string[] args)

{

var directions = new List<string>()

{

"South East",

"North West",

"East",

"South West",

"North",

"West",

"North East",

"South"

};

directions.Sort(new ReversedComparer());

foreach (var direction in directions)

Console.WriteLine(direction);

Console.ReadLine();

}

2. List<T>.OrderBy()

OrderBy method is an element of LINQ and the same as Sort, by default it sorts strings in alphabetical order. In the background it also uses Quicksort algorithm however it implements additional mechanism which checks the initial order when two comparing keys are equal. As the result of what that implementation can be considered as stable. The other difference between Sort and OrderBy is not changing original collection. OrderBy returns ordered items as new object type IOrderedEnumerable<T>, so after sorting to work with newly ordered items you need to use either the new object or assign the returned value to the original object.

Let’s then sort. As you can see below, statement is slightly more complicated than earlier but still very easy. Firstly, OrderBy doesn’t have implementation which not takes any arguments. We need to pass at least one which defines the key which is used to sort. Our collection contains just strings, so we can easily define the key using simple lambda expression x => x. Secondly, we’d like to assign ordered collection to the original one and still use the same object called directions. To do so, we need to convert result of OrderBy which in our case is IOrderedEnumerable<string> to list with ToList function.

directions = directions.OrderBy(x => x).ToList();

1	directions = directions.OrderBy(x => x).ToList();

The result is predictable, which is list of our directions in alphabetical order.

East
North
North East
North West
South
South East
South West
West

East

North

North East

North West

South

South East

South West

West

Now it’s time to make OrderBy working with our custom algorithm. Again we’d like to sort strings in alphabetical order starting comparison from the end of those strings and not as default from beginning.

2.a. IComparer<string> comparer

OrderBy function is overloaded and there is a variant with two input arguments. First is key selector as previously and second one is argument which accepts objects implementing IComparer<T>. As you can see it’s exactly the same option as the one on Sort function. As we already implemented comparer class, let’s reuse it here.

directions = directions.OrderBy(x => x, new ReversedComparer()).ToList();

1	directions = directions.OrderBy(x => x, new ReversedComparer()).ToList();

In the result we can see sorted collection with our custom algorithm.

North
South
East
North East
South East
West
North West
South West

North

South

East

North East

South East

West

North West

South West

And full scope is here.

using System;
using System.Collections.Generic;
using System.Linq;

namespace StringSorting
{
    class Program
    {
        static void Main(string[] args)
        {
            var directions = new List<string>()
            {
                "South East",
                "North West",
                "East",
                "South West",
                "North",
                "West",
                "North East",
                "South"
            };

            directions = directions.OrderBy(x => x, new ReversedComparer()).ToList();

            foreach (var direction in directions)
                Console.WriteLine(direction);

            Console.ReadLine();
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

namespace StringSorting

{

class Program

{

static void Main(string[] args)

{

var directions = new List<string>()

{

"South East",

"North West",

"East",

"South West",

"North",

"West",

"North East",

"South"

};

directions = directions.OrderBy(x => x, new ReversedComparer()).ToList();

foreach (var direction in directions)

Console.WriteLine(direction);

Console.ReadLine();

}

Summary

To sum up I hope you find this article useful. The example used here of sort algorithm is very simple, however it was intention just for training purposes. In your application you can implement much more complex methods depending on your needs.