Order by different Enum property each row

Question

So I have a list of DefaultSearchModal items that have an enum called TypeSearch in every list item. I would like to order the list to have a different enum property each row.

So if you have an unordered list by this:

1,1,2,2,3,3,4,4,5,5,5,5,5,5

I would like to order it to:

1,2,3,4,5,1,2,3,4,5,5,5,5,5

What would be a good algorithm to sort it like this?

    public class DefaultSearchModel
{
    public int Id { get; set; }
    public string Title { get; set; }
    public string Description { get; set; }
    public string Url { get; set; }
    public TypeSearch TypeSearch { get; set; }
}

public enum TypeSearch
        {
           News = 0,
           Blog = 1,
           Photo = 3,
           Page = 4
        }

Answer 1

Personally I would just put it in a loop Here's psudo code for it.

while mainList has items
{
  find first 0 item.
  add to queue, 
  remove from mailList

  find first 1 item 
  add to queue, 
  remove from mailList

  find first 3 item.
  add to queue, 
  remove from mailList

  find first 4 item.
  add to queue, 
  remove from mailList
}

return queue

Answer 2

The end result thanks to bowlturner:

  private IEnumerable<DefaultSearchModel> Sort(IList<DefaultSearchModel> items)
    {
        var returnList = new Collection<DefaultSearchModel>();

        while (items.Any())
        {
            foreach (var type in Enum.GetValues(typeof (TypeSearch)))
            {
                if (items.Any(x => x.TypeSearch == (TypeSearch) type))
                {
                    var item = items.FirstOrDefault(x => x.TypeSearch == (TypeSearch) type);
                    returnList.Add(item);
                    items.Remove(item);
                }
            }
        }

        return returnList;
    }

Answer 3

My FP-flavored solution:

IEnumerable<DefaultSearchModel> DoMagic(IEnumerable<DefaultSearchModel> models)
{
    var groups = models.GroupBy(model => model.TypeSearch);
    var solution = Enumerable
        .Range(0, groups.Max(grp => grp.Count()))
        .SelectMany(i => groups
            .Where(grp => grp.Count() > i)
            .Select(grp => grp.ElementAt(i))
            .OrderBy(model => model.TypeSearch));
    return solution;
}

Probably not most efficient either (since I pointed out that @Jamie's solution isn't, I can't be a hypocrite), but it is not my point right now. I just wanted to show how terse and non-imperative LINQ can be.

Note that we are not repeatedly looking for TypeSearch values that aren't on the list at all, or whose count is beyond a specific treshold.

Answer 4

1. Go once through the list and divide them up in 5 sets.
2. Then simply take one object (if available) from each set in order, and put them into your output list
3. Repeat step 2 until all sets are empty

Algorithm has O(n)