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.
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.
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();
}
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
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.
精彩评论