CODEWITHSUNDEEP
c#sorting
user1196549
user1196549

Reputation:

How to create a sorting index in C#?

I have an array of values and I want to create a sorting index, i.e. an auxiliary array of integers that lists the element in sorted order by indirect addressing.

In other words,

I <= J -> Value[Index[I]] <= Value[Index[J]]

How can I define a comparator for the Sort method to achieve that ? The array of values must remain unchanged.

Upvotes: 0

Views: 297

Answers (1)

Ivan Stoev
Ivan Stoev

Reputation: 205629

The easiest way to build such an index I see is to use LINQ:

var Index = Enumerable.Range(0, Value.Length).OrderBy(i => Value[i]).ToArray();

or if you insist on using Array.Sort, then you can use the overloads that accept Comparison<T> delegate:

var Index = new int[Value.Length];
for (int i = 0; i < Index.Length; i++)
    Index[i] = i;
Array.Sort(Index, (a, b) => Comparer<Value_Type>.Default.Compare(Value[a], Value[b]));

where the Value_Type is the type of the Value array elements.

Another option (IMO the best) is to create a reusable generic comparer like this:

public static class Comparers
{
    public static IComparer<int> CreateIndexComparer<T>(this IReadOnlyList<T> source, IComparer<T> comparer = null)
    {
        return new ListIndexComparer<T>(source, comparer);
    }

    private sealed class ListIndexComparer<T> : Comparer<int>
    {
        readonly IReadOnlyList<T> list;
        readonly IComparer<T> comparer;
        public ListIndexComparer(IReadOnlyList<T> list, IComparer<T> comparer = null)
        {
            this.list = list;
            this.comparer = comparer ?? Comparer<T>.Default;
        }
        public override int Compare(int x, int y)
        {
            return x != y ? comparer.Compare(list[x], list[y]) : 0;
        }
    }
}

and use it with the Array.Sort overloads that accept IComparer<T>:

Array.Sort(Index, Value.CreateIndexComparer());

Upvotes: 1

Related Questions