0

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.

Improve this question
4
  • The implementation might require a different approach if the array is very large or when the objects are mutable (or both). In these cases it might be worth it to sort on insert. Commented Jul 31, 2016 at 8:51
  • The array is large and holds scalars. What do you mean by "sort on insert" ? Commented Jul 31, 2016 at 9:18
  • Sort on insert would mean that you insert the items in such a way that the array is always sorted. That way insertion is more expensive but there is no need to sort the array anymore (if the items are immutable) Commented Jul 31, 2016 at 12:58
  • @ErnodeWeerd: I am working with arrays so insertion can take linear time. Thus the whole insertion process could be O(N²), which is completely unacceptable. I don't see how this could help. Commented Jul 31, 2016 at 14:09

1 Answer 1

Reset to default
1

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());
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Yep, I indeed prefer the Sort version for efficiency reasons (my array holds a million values). Seems that your second option is what I need. I was wondering how to pass the array Value and I didn't think of lambdas.
Mh, the "Sort" solution keeps saying "Error 1 Cannot convert lambda expression to type 'System.Array' because it is not a delegate type"
Hmm, Index is int[], right? My test is hitting either this or this. Here is the test var Value = new[] { "C", "A", "D", "B" }; var Index = Enumerable.Range(0, Value.Length).ToArray(); Array.Sort(Index, Value.CreateIndexComparer());
I am refering to the second solution, with a lambda.
In the end it works with the following syntax (the compiler seems to have trouble resolving some overloads): Array.Sort(Index, (P, Q) => Y[P].CompareTo(Y[Q]));
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.