Reputation: 40341
What is the best algorithm to take array like below:
A {0,1,2,3}
I expected to order it like array below:
B {3,1,0,2}
Any ideas?
Upvotes: 1
Views: 3986
Reputation: 10035
Here's my implementation of the comparer (uses LINQ, but can be easily adapted to older .net versions). You can use it for any sorting algorithms such as Array.Sort, Enumerable.OrderBy, List.Sort, etc.
var data = new[] { 1, 2, 3, 4, 5 };
var customOrder = new[] { 2, 1 };
Array.Sort(data, new CustomOrderComparer<int>(customOrder));
foreach (var v in data)
Console.Write("{0},", v);
The result is 2,1,3,4,5,
- any items not listed in the customOrder are placed at the end in the default for the given type (unless a fallback comparator is given)
public class CustomOrderComparer<TValue> : IComparer<TValue>
{
private readonly IComparer<TValue> _fallbackComparer;
private const int UseDictionaryWhenBigger = 64; // todo - adjust
private readonly IList<TValue> _customOrder;
private readonly Dictionary<TValue, uint> _customOrderDict;
public CustomOrderComparer(IList<TValue> customOrder, IComparer<TValue> fallbackComparer = null)
{
if (customOrder == null) throw new ArgumentNullException("customOrder");
_fallbackComparer = fallbackComparer ?? Comparer<TValue>.Default;
if (UseDictionaryWhenBigger < customOrder.Count)
{
_customOrderDict = new Dictionary<TValue, uint>(customOrder.Count);
for (int i = 0; i < customOrder.Count; i++)
_customOrderDict.Add(customOrder[i], (uint) i);
}
else
_customOrder = customOrder;
}
#region IComparer<TValue> Members
public int Compare(TValue x, TValue y)
{
uint indX, indY;
if (_customOrderDict != null)
{
if (!_customOrderDict.TryGetValue(x, out indX)) indX = uint.MaxValue;
if (!_customOrderDict.TryGetValue(y, out indY)) indY = uint.MaxValue;
}
else
{
// (uint)-1 == uint.MaxValue
indX = (uint) _customOrder.IndexOf(x);
indY = (uint) _customOrder.IndexOf(y);
}
if (indX == uint.MaxValue && indY == uint.MaxValue)
return _fallbackComparer.Compare(x, y);
return indX.CompareTo(indY);
}
#endregion
}
Upvotes: 2
Reputation: 107
Could the issue be resolved using a Dictionary so the elements have a relationship that isn't predicated on sort order at all?
Upvotes: 1
Reputation: 11662
What you need to do is determine the ordering of B and then apply that ordering to A. One way to accomplish this is to undo the ordering of B and keep track of what happens along the way. Then you can do the reverse to A.
Here's some sketchy C# (sorry, I haven't actually run this)...
Take a copy of B:
List<int> B2 = new List<int>(B);
Now sort it, using a sort function that records the swaps:
List<KeyValuePair<int,int>> swaps = new List<KeyValuePair<int,int>>();
B2.Sort( delegate( int x, int y ) {
if( x<y ) return -1;
if( x==y ) return 0;
// x and y must be transposed, so assume they will be:
swaps.Add( new KeyValuePair<int,int>(x,y) );
return 1;
});
Now apply the swaps, in reverse order, to A:
swaps.Reverse();
foreach( KeyValuePair<int,int> x in swaps )
{
int t = A[x.key];
A[x.key] = A[x.value];
A[x.value] = t;
}
Depending how the built-in sort algorithm works, you might need to roll your own. Something nondestructive like a merge sort should give you the correct results.
Upvotes: 3
Reputation: 37830
If they are nearly the same then here is some pseudo code:
Make an ArrayList
Copy the contents of the smaller array to the arraylist
for each item I in the larger array
FInd I in the ArrayList
Append I to a new array
Remove I from the arraylist
Upvotes: 1
Reputation: 40341
Both array's contain the same values (or nearly so) but I need to force them to be in the same order. For example, in array A the value "3045" is in index position 4 and in array B it is in index position 1. I want to reorder B so that the index positions of like values are the same as A.
Upvotes: 1
Reputation: 43228
In the example you gave (an array of numbers), there would be no point in re-ordering A, since you could just use B.
So, presumably these are arrays of objects which you want ordered by one of their properties.
Then, you will need a way to look up items in A based on the property in question (like a hashtable). Then you can iterate B (which is in the desired sequence), and operate on the corresponding element in A.
Upvotes: 1
Reputation: 37830
So if you have two arrays and they hold the same data just in different order then just do this:
A = B
I suspect that is not your situation so I think we need more info.
Upvotes: 6