В момента имам сортиране чрез сливане, което сортира списък с възли според цяло число във всеки възел, наречено „F“ (So Node.F).
Въпреки това измислих нужда да използвам MergeSort за друг списък с обекти - Entities. Искам обаче да сортирам това според цяло число във всеки обект, наречен "AmountEaten" (така че Entity.AmountEaten).
Сега тук е моят проблем -> да накарам класа MergeSort да работи за всички обекти. Вече замених всички препратки към Node в рамките на сортирането с „обект“, но как да разреша потребителски критерии за сортиране? Има ли начин да го предоставя като параметър.
Ако това няма смисъл, в рамките на MergeSort сравнявам две стойности (напр. Left.F ‹ Right.F). С общ обект това не работи, защото F не съществува. Бих искал да мога да сравня всичко в рамките на обекта, вътре в моя сорт (напр. Left.AmountEaten ‹ Right.AmountEaten). Не мога да разбера как да дам това като параметър. Веднага се сетих за Delegates, но не съм сигурен как/дали това е правилно.
Тъй като сортирането се занимава със списъци, а не с отделни обекти, не мога просто да дам параметър на F/AmountEaten, тъй като бих искал да получа достъп до променливата, а не до стойността.
Ако имате нужда от повече подробности/не разбирате, моля, попитайте.
Изглежда стигнах до някакво заключение, но можете ли да ми помогнете да го накарам да работи?
Клас на MergeSort:
static class MergeSort
{
public static IList<object> Sort(IList<object> input, Comparison<object> comparison /* Comparison is a delegate that works out the difference
* between 2 values - Same signature used by List<T>.Sort */)
{
List<object> Result = new List<object>();
Queue<object> Left = new Queue<object>(); //Switched from lists to queues because removing at index 0 is more efficient
Queue<object> Right = new Queue<object>();
//Dequeue() and Count() have a time complexity of O(1)
if (input.Count <= 1)
return input;
int midpoint = input.Count / 2;
for (int i = 0; i < midpoint; i++)
Left.Enqueue(input[i]);
for (int i = midpoint; i < input.Count; i++)
Right.Enqueue(input[i]);
Left = new Queue<object>(Sort(Left.ToList(), comparison)); //Recursion! :o
Right = new Queue<object>(Sort(Right.ToList(), comparison)); ; //This line and the one above split the list into smaller lists (left and right)
Result = Merge(Left, Right, comparison); //This joins the lists together
return Result;
}
private static List<object> Merge(Queue<object> Left, Queue<object> Right, Comparison<object> comparison)
{
int cmp = comparison(Left.Peek(), Right.Peek());
//If cmp is less than 0, left is less. If it is greater, left is greater
List<object> Result = new List<object>();
while (Left.Count /* O(1) operation */ > 0 && Right.Count > 0)
{
if (cmp < 0)
Result.Add(Left.Dequeue());
//Left.RemoveAt(0) - Using a list to remove at a certain point is inefficient
else
Result.Add(Right.Dequeue());
}
while (Left.Count > 0)
Result.Add(Left.Dequeue());
while (Right.Count > 0)
Result.Add(Right.Dequeue());
return Result;
}
}
}
Употреба:
Entities = MergeSort.Sort(Entities, (p, q) => p.F.CompareTo(q.F)).ToList();