7
\$\begingroup\$

I wrote a stable sort algorithm in C#. It is just a simple iteration, and is probably not very optimal:

static void StableSort(ref ObservableCollection<string> Vals, ref ObservableCollection<int> Weight)
{
  for (int i = 0; i < Vals.Count; i++)
  {
    int LargestVal = -1;
    int LargestValIndex = 0;

    for (int j = i; j < Vals.Count; j++)
    {
      if (Weight[j] > LargestVal)
      {
        LargestVal = Weight[j];
        LargestValIndex = j;
      }
    }

    if (LargestValIndex != i)
    {
      Weight.Insert(i, Weight[LargestValIndex]);
      Weight.RemoveAt(LargestValIndex + 1);

      Vals.Insert(i, Vals[LargestValIndex]);
      Vals.RemoveAt(LargestValIndex + 1);
    }
  }
}

You can see how it works by running it with this code (this isn't what I want a review on, but if you see something really wrong, please tell me):

static void Main(string[] args)
{
  ObservableCollection<int> i = new ObservableCollection<int>() { 1, 2, 4, 6, 7, 2, 4, 7, 3, 3, 7 };
  ObservableCollection<string> s = new ObservableCollection<string>() { "1", "2a", "4a", "6", "7a", "2b", "4b", "7b", "3a", "3b", "7c" };

  foreach (int item in i)
  {
    Console.Write(item + ", ");
  }
  Console.WriteLine();

  foreach (string item in s)
  {
    Console.Write(item + ", ");
  }
  Console.WriteLine();

  StableSort(ref s, ref i);
  Console.WriteLine();

  foreach (int item in i)
  {
    Console.Write(item + ", ");
  }
  Console.WriteLine();

  foreach (string item in s)
  {
    Console.Write(item + ", ");
  }
  Console.WriteLine();
}

This is going to be integrated into a larger project that requires that I use ObservableCollections. At the most, there will probably be 20-50 values being sorted, but this is going to be run on phones and other devices without a lot of computing power, so I would also like to know if this should be optimized or if a different sorting method should be used to improve performance. A stable sort isn't absolutely required, but I would much prefer it. Thanks for any tips ahead of time!

\$\endgroup\$
  • \$\begingroup\$ Sorting is hard and probably deserves proper unit tests. \$\endgroup\$ – RubberDuck Dec 18 '14 at 5:24
  • \$\begingroup\$ Oh. Yeah. Sure. Sorry. I mean it would be better to Assert that you're getting the expected answer using a unit testing framework than to visually check it by writing results results to the console. msdn.microsoft.com/en-us/library/ms182532.aspx \$\endgroup\$ – RubberDuck Dec 18 '14 at 5:29
  • \$\begingroup\$ Sorting is hard so unless you are 100% confident with your solution then I suggest you use the sort methods that come with the .net framework for your production code. \$\endgroup\$ – Tien Dinh Dec 27 '14 at 17:13
  • \$\begingroup\$ If my developers were to write a sorting algorithm then I demand them to also write a 50 page document fully describe their code and why they choose to reinvent the wheels rather then using one of the exisiting methods provided \$\endgroup\$ – Tien Dinh Dec 27 '14 at 17:16
4
\$\begingroup\$

Possible problems

  • you don't check for Vals == null nor for Weigth == null
  • you don't check if Vals.Count == Weight.Count
  • a object which subscribed the CollectionChanged Event of the collection, will get much work

Guard condition

If we replace

if (LargestValIndex != i)
{
    //do the swapping
}  

by

if (LargestValIndex == i) { continue; }

// do the swapping  

we will save a level of indention.

Naming

  • Based on the naming guidelines parameters and local variables should be named using camelCase casing.
  • Because an ObservableCollection will by its nature contain multiple items, a parameter representing one should be named using the plural form.

Refactoring

Implementing all above will lead to

static void StableSort(ref ObservableCollection<string> values, ref ObservableCollection<int> weights)
{
    if (values == null) { throw new ArgumentNullException("values"); }
    if (weights == null) { throw new ArgumentNullException("weights"); }

    if (values.Count != weights.Count) { throw new ArgumentOutOfRangeException("collections count not equal", (Exception)null); }

    IList<string> localValues = new List<string>(values);
    IList<int> localWeights = new List<int>(weights);

    for (int i = 0; i < values.Count; i++)
    {
        int largestWeight = -1;
        int largestWeightIndex = 0;

        for (int j = i; j < values.Count; j++)
        {
            if (localWeights[j] > largestWeight)
            {
                largestWeight = localWeights[j];
                largestWeightIndex = j;
            }
        }

        if (largestWeightIndex == i) { continue; }

        localWeights.Insert(i, localWeights[largestWeightIndex]);
        localWeights.RemoveAt(largestWeightIndex + 1);

        localValues.Insert(i, localValues[largestWeightIndex]);
        localValues.RemoveAt(largestWeightIndex + 1);
    }

    values = new ObservableCollection<string>(localValues);
    weights = new ObservableCollection<int>(localWeights);

}  

now that it is a clean implementation we are finished.

But wait, we can do better.

We can use the OrderByDescending() extension method together with Select() extension method and anonymous types.

static void StableSort(ref ObservableCollection<string> values, ref ObservableCollection<int> weights)
{
    if (values == null) { throw new ArgumentNullException("values"); }
    if (weights == null) { throw new ArgumentNullException("weights"); }

    if (values.Count != weights.Count) { throw new ArgumentOutOfRangeException("collections count not equal", (Exception)null); }

    IList<string> localValues = new List<string>();
    IList<int> localWeights = new List<int>();

    int index = -1;
    var weightsWithIndex = weights.Select(p => new { Value = p, Index = ++index }).OrderByDescending(p => p.Value);

    foreach (var w in weightsWithIndex)
    {
        localWeights.Add(w.Value);
        localValues.Add(values[w.Index]);
    }

    values = new ObservableCollection<string>(localValues);
    weights = new ObservableCollection<int>(localWeights);
}

So, what is this fancy, cool stuff

weights.Select(p => new { Value = p, Index = ++index })

??

We create for each item in weights a anonymous type where we create a property Value and assign the item of weights and before we assign the index to the Index property we increment it. So basically this is just like creating a Tuple but a way cooler.

Some related information

  • by definition anonymous types are immutable.
  • the order of properties matters

    var p1 = new { X=1, Y=2 };
    var p2 = new { X=1, Y=2 };
    var p3 = new { Y=2, X=1 };  
    

    here p1.Equals(p2) == true but p1.Equals(p3) == false

    An extract from a good reading about this subject

    In short, an anonymous type is a reference type that derives directly from object and is defined by its set of properties base on their names, number, types, and order given at initialization. In addition to just holding these properties, it is also given appropriate overridden implementations for Equals() and GetHashCode() that take into account all of the properties to correctly perform property comparisons and hashing. Also overridden is an implementation of ToString() which makes it easy to display the contents of an anonymous type instance in a fairly concise manner.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.