ordered swap on simple collection

Question

I have a method that swaps two items:

swap( collection['a'], collection['b'] );  // result = 'b', 'a'
swap( collection[0], collection[1] ); // result = collection[1], collection[0]
swap( 0, collection.indexOf(collection[1]) ); // result collection[1] index, 0

• The swap method cannot be modified.
• Four possible values stored in a collection: 'a', 'b', 'c', 'd'
• Swapped to always be in this order 'd', 'b', 'a', 'c'
• Any of the four possible values may or may not be in the collection

Please help me to implement this algorithm.

Thanks!

For those that care, this is not homework.

Examples:

//Example 1:
//collection contains: 'a', 'b', 'c', 'd'
//desired order: 'd', 'b', 'a', 'c'
swap(0, collection.IndexOf(collection['d']));
swap(1, collection.IndexOf(collection['b']));
swap(2, collection.IndexOf(collection['a']));
swap(3, collection.IndexOf(collection['c']));

//Example 2:
//collection contains: 'a', 'b', 'c'
//desired order: 'b', 'a', 'c' 
swap(0, collection.IndexOf(collection['b']));
swap(1, collection.IndexOf(collection['a']));
swap(2, collection.IndexOf(collection['c']));

Answer 1

Basically, you're looking for a sort with an indirect comparison. I.e., instead of comparing the letters themselves, you compare values they look up in a table. If you'll pardon C++ syntax, the general idea would be something like this:

class my_cmp { 
    static const int positions[] = { 2, 1, 3, 0};
public:
    bool operator<(char a, char b) { 
        return positions[a-'a'] < positions[b-'a'];
    }
}:

std::sort(collection.begin(), collection.end(), my_cmp());

std::sort will use swap to move the elements in the collection. Although the syntax will obviously be a little different, from what I remember when I last used it, the same general idea should apply reasonably well to C# as well.

Answer 2

I realize now (thanks to those that answered) that using a custom IComparer like this below removes the need to use swap. This solution guarantees the order and will still work correctly when one of the 5 possible values is missing.

class CustomOrder : IComparer<Series>
{
    static readonly Dictionary<string, int> dictionary = 
        new Dictionary<string, int>() 
    { 
        {"Excellent", 1}, 
        {"Very Good", 2},
        {"Average", 3},
        {"Bad", 4},
        {"Very Bad", 5}
    };

    public int Compare(Series x, Series y)
    {
        return dictionary[x.Name].CompareTo(dictionary[y.Name]);
    }
}

public partial class _Default : System.Web.UI.Page
{
    protected void Page_Load(object sender, EventArgs e)
    {
        Series[] sortedSeries = chart.Series.ToArray();
        Array.Sort(sortedSeries, new CustomOrder());
    } 
}

Old solution using swap (for reference)

I don't like it, but this seems to work. Anyone have any better ideas?

int count = collection.Count;

// don't need to swap if there is only one element
if (count > 1)
{
    // have to run once for each letter 
    sortCollection(count);
    sortCollection(count);      
    sortCollection(count);
    sortCollection(count);
}

private void sortCollection(int count)
{
    if (collection.Contains(collection['c']))
    {
        // take care of last element
        collection.Swap(count - 1, collection.IndexOf(collection['c']));
    }
    if (collection.Contains(collection['a']) && collection.Contains(collection['b']))
    {
        // take care of middle elements
        if(collection[1] != collection['b'])
        collection.Swap(collection['a'], collection['b']);
    }
    if (collection.Contains(collection['d']))
    {
        // take care of first element
        if(collection[0] != collection['d'])
        collection.Swap(0, collection.IndexOf(collection['d']));
    }
}

Answer 3

Jerry's C++ solution adapted to C#:

using System;
using IComparer = System.Collections.IComparer;

class CustomOrder: IComparer
{
    static readonly int[]   positions = { 2, 1, 3, 0 };

    public int Compare( object x, object y )
    {
        return positions[(char)x-'a'].CompareTo( positions[(char)y-'a'] );
    }
}

class Startup
{
    static void Main(string[] args)
    {
        char[]  collection  = {'a', 'b', 'c', 'd'};

        Console.WriteLine( collection );            // abcd
        Array.Sort( collection, new CustomOrder() );
        Console.WriteLine( collection );            // dbac
    }
}

Cheers & hth.,

– Alf