Reorder an IList using the minimum number of Inserts and Removes

Question

I need an extension method that takes two arguments: a target IList<T> and a custom comparer.

public static void CustomSort<T>( IList<T> target, IComparer<T> comparer )
{
    ...
}

The extension method's job is to arrange target's elements in the order indicated by the custom comparer.

Here are some solutions that won't work:

• The List<T>.Sort does in-place sorting, which is basically what I'm after. But I can't assume target's concrete type is List<T>.
• LINQ offers some solutions but unfortunately they output their results as a new enumerable instead of modifying the target list.

Instead, I need the target's Remove and Insert methods to be called to put its elements into the right order. The target list may be observable so it is important that the solution does not do more removes and inserts than are necessary to obtain the desired order.

Answer 1

I think something like this will do you.

We sort an array of offsets, then determine the set of deltas that need to be applied and finally apply them to produce the newly ordered IList.

public static void CustomSort<T>( IList<T> list , IComparer<T> comparer )
{
  int[] unsorted = Enumerable.Range(0,list.Count).ToArray() ;
  int[] sorted   = Enumerable.Range(0,list.Count).OrderBy( x => list[x] , comparer ).ToArray() ;
  var   moves    = sorted.Zip( unsorted , (x,y) => new{ Src = x , Dest = y , } ).Where( x => x.Src != x.Dest ).OrderBy( x => x.Src ).ToArray() ;

  // at this point, moves is a list of moves, from a source position to destination position.
  // We enumerate over this and apply the moves in order.
  // To do this we need a scratch pad to save incomplete moves, where an existing item has
  // been over-written, but it has not yet been moved into its final destination.

  Dictionary<int,T> scratchPad = new Dictionary<int, T>() ; // a parking lot for incomplete moves
  foreach ( var move in moves )
  {
    T value ;

    // see if the source value is on the scratchpad.
    // if it is, use it and remove it from the scratch pad.
    // otherwise, get it from the indicated slot in the list.
    if ( scratchPad.TryGetValue( move.Src , out value ) )
    {
      scratchPad.Remove( move.Src );
    }
    else
    {
      value = list[ move.Src ] ;
    }

    // if the destination is after the source position, we need to put
    // it on the scratch pad, since we haven't yet used it as a source.
    if ( move.Dest > move.Src )
    {
      scratchPad.Add( move.Dest , list[ move.Dest ]);
    }

    // finally, move the source value into its destination slot.
    list[ move.Dest ] = value ;

  }

  return ;
}

Answer 2

The comments show that this can actually be a difficult problem, as stated. So what if we take this problem from different angles:

1. Why are the observers of this collection take so long? They should only do fast things in response to individual changes. E.g. if it's for a UI change, it could wait until the next UI redraw before caring about the changes. That should let the whole reorder finish in one go. Or
2. Use something like ObservableRangeCollection<T> so that you've got an AddRange on observable collections. Some simple code can determine if the collection is List<T> or ObservableRangeCollection<T> to use AddRange if possible.

E.g.

public static void SmartSort<T>(IList<T> source)
{
    var sortedList = source.OrderBy(x => x).ToList();
    if (source.SequenceEqual(sortedList))
        return;
    var list = source as List<T>;
    var collection = source as ObservableRangeCollection<T>;
    if (list != null)
    {
        list.Clear();
        list.AddRange(sortedList);
    }
    else if (collection != null)
        collection.ReplaceRange(sortedList);
    else
    {
        for (int i = 0; i < source.Count; i++)
            source[i] = sortedList[i];
    }
}

Answer 3

1. Use the LINQ extension method to sort and get a new List implicitly calling ToList() at the end;

2. Then tell your observable list to suspend itself (do not care about changes)

3. Clear your observable list

4. Add items to the observable list from the linq-ordered list.

5. Tell your observable list to resume watching for changes

It's efficient concerning the number of changes the observables watches; From the algorithm efficiency point of view i'd give a try to this solution. You might never need to optimize any further. Remember: premature optimization is the root of all evil