Sorting a list wrapper class

Question

I have a class that wraps a List and adds functionality for dealing with ratios. It needs to be sorted two ways at different times; by ordinal position, and by the amount of the ratio.

Below is the method I am currently using to do the sort by ordinal position which I want to use as the basis for two related questions:

1. Is there a more perfomant way to do this?
2. How would I do this using an IComparer?

The primary motivation for passing in the IComparer would be to allow for different implementations to randomly shuffle the list. This post seems to address the same issue but without any resolution in code that I can see. I'm looking for some sample code and usage of it so I can wrap my head around it.

Cheers,
Berryl

/// <summary>
/// Maintains a list of ratios suitable for use in an allocation when the
/// sum of all items is exactly equal to one (100%). No individual it may
/// be less than zero or greater than one.
/// </summary>
public class RatioBag : IList<RatioAssociation>
{
    private readonly IList<RatioAssociation> _items = new List<RatioAssociation>();

    private Random _rnd;

    public void Order(IndexOrdering ordering) {
        IList<RatioAssociation> ordered = null;
        switch (ordering)
        {
            case IndexOrdering.FirstToLast:
                break;
            case IndexOrdering.LastToFirst:
                ordered = this.Reverse().ToList();
                break;
            case IndexOrdering.Random:
                if (_rnd == null) _rnd = new Random();
                ordered = Enumerable.Range(0, Count)
                    .OrderBy(x => _rnd.Next())
                    .Select(index => this[index])
                    .ToList();
                break;
            default:
                throw new ArgumentOutOfRangeException("ordering");
        }
        if (ordered == null) return;

        Clear();
        foreach (var ra in ordered) {
            Add(ra);
        }
    }

Answer 1

The performance of your approach is not optimal, because you aren't doing an in place sort. Instead you are copying each item twice. First in the call to ToList and then in the call to Add.

The IComparer interface is used in combination with the List.Sort method that does an in place sort. So that should be the way to go.

---

You would first need to change the type of _items to List<RatioAssociation>.

For each ordering you want to support, you would need to create a new class that implements IComparer. If these classes wouldn't be used else where you could put them as private classes inside RatioBag.

Your Order method would then look something like this:

public void Order(IndexOrdering ordering)
{
    switch (ordering)
    {
        case IndexOrdering.FirstToLast:
            _items.Sort(new AscendingComparer());
            break;
        case IndexOrdering.LastToFirst:
            _items.Sort(new DescendingComparer());
            break;
        case IndexOrdering.Random:
            _items.Sort(new RandomComparer());
            break;
        default:
            throw new ArgumentOutOfRangeException("ordering");
    }
}

However, I would suggest to remove the IndexOrdering enum and provide one ordering method per ordering type. The code would be cleaner.

Answer 2

Off hand, I don't really see much you could do to make it faster, aside from avoiding calling this method as much as possible, as sorting and rebuilding lists is inherently slow :-). One possible option would be to use a SortedSet, which would keep the collection in sorted order and thereby help you avoid the costs associated with resorting every time you change the collection. Doesn't help much though I suppose when you're changing the sort strategy (although I'd bet the SortedSet implementers gave that some thought when they wrote the code).

This doesn't really answer your question I suppose, but instead of passing an IComparer, could you instead pass a Func<...> to your Order() method (and ditch the IndexOrdering enum), and then pass that Func straight into the OrderBy() method? This would allow you to express all sorts of crazy sort methods without having to touch this class, and you could remove any unnecessary state baggage (like _rnd, if it's not used anywhere else) from this class.

Something like:

public class RatioBag : IList<RatioAssociation>
{
    private readonly IList<RatioAssociation> _items = new List<RatioAssociation>();

    public void Order(Func<RatioAssociation, int> func) {
        var ordered = _items.OrderBy(func);
        _items.Clear();
        ((List<RatioAssociation>)_items).AddRange(ordered);
    }
}

then, to call it:

var myCollection = new RatioBag();
myCollection.Order(item => item.PropertyX);
myCollection.Order(item => item.PropertyY);
var r = new Random();
myCollection.Order(item => r.Next());

The IComparer solution would also achieve a similar solution.

Hope this helps.

Nate

Answer 3

Why should not to use three different methods instead of one?