CODEWITHSUNDEEP
c#arrayslinqlistsorting
user4095615
user4095615

Reputation:

Get new indices of items in a collection after sorting using LINQ

I want to sort a list (or array) in C# and want to save the new indexes for each of the items in the unsorted list. I.e.:

A = 2 3 1

sorted(A) = 1 2 3

indexes = 1 2 0 <-- This is what I need

I read on Stack overflow that LINQ is particularly useful, but I cannot find how to do this specifically.

Upvotes: 18

Views: 5174

Answers (5)

nawfal
nawfal

Reputation: 73253

Note:

I made a terrible mistake of misreading OP's question (and embarrassed this received so many upvotes). I wished (ideally) OP accepts one of the other answers as correct. To do justice to the upvoters and in spirit of SO, I will amend this answer to make it correct.

One could carry two extension methods, one for old indices and one for new indices (which is what OP wants).

public static IEnumerable<int> OldIndicesIfSorted<T>(this IEnumerable<T> source) where T : IComparable<T>
{
    return source
        .Select((item, index) => new { item, index })
        .OrderBy(a => a.item)
        .Select(a => a.index);
}

public static IEnumerable<int> NewIndicesIfSorted<T>(this IEnumerable<T> source) where T : IComparable<T>
{
    return source
        .OldIndicesIfSorted()
        .Select((oldIndex, index) => new { oldIndex, index })
        .OrderBy(a => a.oldIndex)
        .Select(a => a.index);
}

Call it like,

//A = [2, 3, 1];
A.NewIndicesIfSorted(); // should print [1, 2, 0]

The two methods are lazy, but NewIndicesIfSorted should ideally be written according to Matthew Watson's answer which is simply more efficient. The plus side of both mine and Mat's answer is that is handles duplicate entries well.

Upvotes: 23

w.b
w.b

Reputation: 11238

Another working solution:

var input = new List<int> { 2, 3, 1 };
var result = input.Select(x => input.OrderBy(n => n).ToList().IndexOf(x));

Console.WriteLine(String.Join(" ", result));  // 1 2 0

Upvotes: 1

Matthew Watson
Matthew Watson

Reputation: 109762

One way to do this is as follows:

int[] a = {2, 3, 1};
int[] b = Enumerable.Range(0, a.Length).ToArray();
int[] c = new int[a.Length];

Array.Sort(a, b);

for (int i = 0; i < b.Length; ++i)
    c[b[i]] = i;

Console.WriteLine(string.Join(", ", c)); // Prints 1, 2, 0

It uses the overload of Array.Sort() which sorts one array using the values from a different array.

I think this is fairly efficient: It uses a O(N log(N)) sort and an O(N) remapping. (The other correct solutions are O(N log(N)) plus O(N^2))

It only works with arrays, however (because there is no equivalent of Array.Sort() for List).

An alternative using Linq (and effectively an amendment to @nawfal's answer):

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

var b = a
    .Select((item, index) => new { item, index })
    .OrderBy(x => x.item)
    .Select(x => x.index)
    .ToArray();

int[] c = new int[b.Length];

for (int i = 0; i < b.Length; ++i)
    c[b[i]] = i;

Console.WriteLine(string.Join(", ", c)); // Prints 1, 2, 0

The crucial thing here is the additional mapping step in both approaches:

int[] c = new int[b.Length];

for (int i = 0; i < b.Length; ++i)
    c[b[i]] = i;

This is effectively a reverse-lookup mapping.

Upvotes: 4

Verbon
Verbon

Reputation: 545

While reading other answers I got a little confused about which indexes order you want exactly, but here's solution if you want them to in order 1 2 0 as you posted in your question. Try this:

var A = new int[] { 2, 3, 1 };
var indexes = new int [A.Length];

var sorted = A.OrderBy(n => n)
              .Select((n, i) => 
                      { 
                          indexes[Array.IndexOf(A, n)] = i;

                          return n; 
                      })
              .ToArray();

Upvotes: 0

andrew.caunce
andrew.caunce

Reputation: 87

You could do this with a LINQ select:

var a =new [] {2,3,1};

var sorted = a.OrderBy (x => x).ToList();
var indexes = a.Select (x => sorted.IndexOf(x));

If this is a huge list rather than this simple one it might be a little inefficient but does return what you are expecting.

Upvotes: 8

Related Questions