Stable Sort in C#

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!

• Sorting is hard and probably deserves proper unit tests. – RubberDuck Dec 18 '14 at 5:24
• 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 – RubberDuck Dec 18 '14 at 5:29
• 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 Dec 27 '14 at 17:13
• 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 – Tien Dinh Dec 27 '14 at 17:16

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)
{
}

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