Stable Sort in C#

Question

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!

• RubberDuck: Sorting is hard and probably deserves proper unit tests.
• RubberDuck: 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
• Tien Dinh: 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.
• Tien Dinh: 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

Answer 1

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.

• RubberDuck: Hmm I wonder what kind of algorithm is under the hood of OrderByDescending. Nice answer(as always).
• Heslacher: @RubberDuck check it out : referencesource.microsoft.com/#System.Core/System/Linq/…
• RubberDuck: Way ahead of Ya. =;)-