CODEWITHSUNDEEP
c#.netsortingcollections
homie347
homie347

Reputation: 551

C# Sort list while also returning the original index positions?

I'm interested in sorting a collection, but also returning an index which can be used to map to the original position in the collection (before the sort).

Let me give an example to be more clear:

List<int> A = new List<int>(){3,2,1};
List<int> B;
List<int> idx;

Sort(A,out B,out idx);

After which: 

A = [3,2,1] 
B = [1,2,3]
idx = [2,1,0]

So that the relationship between A,B,idx is:

A[i] == B[ idx[i] ] , for i = 0...2

Does C#/.Net have any built in mechanism to make this easy to implement?

Thanks.

Upvotes: 41

Views: 47798

Answers (5)

jmccaffrey
jmccaffrey

Reputation: 1

I typically write a specific function when needed. Less versatile but simpler. For example:

static int[] ArgSort(List<double> lst)
{
  int n = lst.Count;
  int[] idxs = new int[n];
  for (int i = 0; i < n; ++i)
    idxs[i] = i;
  double[] arr = lst.ToArray();
  Array.Sort(arr, idxs);  // sort idxs based on arr vals
  return idxs;
}

Upvotes: 0

Yeldar Kurmangaliyev
Yeldar Kurmangaliyev

Reputation: 34244

As for now, you can also utilize anonymous types or value tuples instead of KeyValuePair. It will provide more precise naming and make your code more readable:

Anonymous types (C# 3.0):

List<int> arr = new List<int>() { 3, 2, 1 };

var sorted = arr
    .Select((x, i) => new { Value = x, OriginalIndex = i }))
    .OrderBy(x => x.Value)
    .ToList();

int originalIndexOfTheSmallestItem = sorted[0].OriginalIndex;

List<int> B = sorted.Select(x => x.Value).ToList();
List<int> idx = sorted.Select(x => x.OriginalIndex).ToList();

Value tuples (C# 7.0):

List<int> arr = new List<int>() { 3, 2, 1 };

var sorted = arr
    .Select((x, i) => (Value: x, OriginalIndex: i))
    .OrderBy(x => x.Value)
    .ToList();

int originalIndexOfTheSmallestItem = sorted[0].OriginalIndex;

List<int> B = sorted.Select(x => x.Value).ToList();
List<int> idx = sorted.Select(x => x.OriginalIndex).ToList();

The difference is that you can return value tuple from your method and use it, but anonymous type can only be used within this method.

Upvotes: 1

Mohamed BenHaddou
Mohamed BenHaddou

Reputation: 131

a somehow more elegant approach using lambda

Array.Sort<int>(idx, (a, b) => A[a].CompareTo(A[b]));

this gives u idx array from the A array

Upvotes: 9

jason
jason

Reputation: 241789

While Mark Byers provided you a solution using LINQ, I want to show you another solution using the .NET Framework.

There is an overload of Array.Sort that will do this for you:

int[] a = new[] { 3, 2, 1 };
int[] p = new[] { 0, 1, 2 };

Array.Sort(a, p);

Assert.IsTrue(a.SequenceEquals(new[] { 1, 2, 3 }));
Assert.IsTrue(p.SequenceEquals(new[] { 2, 1, 0 }));

Thus, here is a generic method meeting your specification that leverages this overload:

void Sort<T>(
    List<T> input,
    out List<T> output,
    out List<int> permutation,
    IComparer<T> comparer
) {
    if(input == null) { throw new ArgumentNullException("input"); }
    if(input.Count == 0) {
        // give back empty lists
        output = new List<T>(); 
        permutation = new List<int>();
        return;
    }
    if(comparer == null) { throw new ArgumentNullException("comparer"); }
    int[] items = Enumerable.Range(0, input.Count).ToArray();
    T[] keys = input.ToArray();
    Array.Sort(keys, items, comparer);
    output = keys.ToList();
    permutation = items.ToList();   
}

Upvotes: 27

Mark Byers
Mark Byers

Reputation: 839144

It can be done quite easily using Linq.

  • Convert your list into a new list of pairs (object, original index of object).
  • Sort the new list by the first item in the pair
  • Extract the sorted list and the original indices.

Here's some code to demonstrate the principle:

List<int> A = new List<int>() { 3, 2, 1 };

var sorted = A
    .Select((x, i) => new KeyValuePair<int, int>(x, i))
    .OrderBy(x => x.Key)
    .ToList();

List<int> B = sorted.Select(x => x.Key).ToList();
List<int> idx = sorted.Select(x => x.Value).ToList();

I think this gives A[idx[i]] = B[i], but that hopefully is good enough for you.

Upvotes: 67

Related Questions