# Sorting algorithm

Posted on

Problem

This is my ugly code which needs to sort my data. I’m not really familiar with C# since actually I’m a Java programmer.

How could this code be rewritten without loosing performance? I know I could use reflection, but it is bad for performance.

`sortings` is a list of the fields that have to be sorted and if it has to be ASC and DESC. `leistungen` is the data to be sorted.

The classes:

``````public class Aufzeichnung
{
public string Mitarbeiter { get; set; }
public int Dauer { get; set; }
public double Kosten { get; set; }
}

public class Leistung
{
public int ID { get; set; }
public string Art { get; set; }
public string Angebot { get; set; }
public string Jahr { get; set; }
public string Berater { get; set; }
public string Assistent { get; set; }
public double Preis { get; set; }
public List<Aufzeichnung> Aufzeichnungen { get; set; }
}

public class LaufendeLeistung
{
public string Kunde { get; set; }
public List<Leistung> Leistungen { get; set; }
}
``````

The algorithm:

``````internal static IEnumerable<A> Sort(List<A> leistungen, IEnumerable<Sorting> sortings)
{
for (int i = 0; i < sortings.Count(); i++)
{
var sort = sortings.ElementAt(i).Ascending ? 1 : -1;

if (sortings.ElementAt(i).Field.Equals("Kunde"))
{
leistungen.Sort((a,b) => string.Compare(a.Kunde,b.Kunde)*sort);
}
else
{
for (var j = 0; j < leistungen.Count(); j++)
{
if (sortings.ElementAt(i).Field.Equals("Leistung"))
{
leistungen[j].Leistungen.Sort((a, b) => string.Compare(a.Art, b.Art) * sort);
}
else if (sortings.ElementAt(i).Field.Equals("Angebot"))
{
leistungen[j].Leistungen.Sort((a, b) => string.Compare(a.Angebot, b.Angebot) * sort);
}
else if (sortings.ElementAt(i).Field.Equals("Jahr"))
{
leistungen[j].Leistungen.Sort((a, b) => string.Compare(a.Jahr, b.Jahr) * sort);
}
else if (sortings.ElementAt(i).Field.Equals("Berater"))
{
leistungen[j].Leistungen.Sort((a, b) => string.Compare(a.Berater, b.Berater) * sort);
}
else if (sortings.ElementAt(i).Field.Equals("Assistent"))
{
leistungen[j].Leistungen.Sort((a, b) => string.Compare(a.Assistent, b.Assistent) * sort);
}
else if (sortings.ElementAt(i).Field.Equals("Mitarbeiter"))
{
for (var k = 0; k < leistungen[j].Leistungen.Count(); k++)
{
if (leistungen[j].Leistungen[k].Aufzeichnungen != null)
{
leistungen[j].Leistungen[k].Aufzeichnungen.Sort((a, b) => string.Compare(a.Mitarbeiter, b.Mitarbeiter) * sort);
}
}

}

}
}
}
return leistungen;
}
``````

Solution

Edit

My original answer does not address ascending / descending sorting dynamically. So here is my idea. Note that this is different from @ratchetFreak answer. The key is that an `IComparer<T>` automatically overrides an object’s `IComparable<T>` implementation.

1. New class, `LeistungComparer : Comparer<T>`
1. `public abstract class Comparer<T> : IComparer<T>` – so inherit and we get the interface.
2. We’ll pass a constructor parameter to tell which way to sort.
2. Move `Leistung.CompareTo()` code to this new class.
3. `Leistung.CompareTo()` will just call the `LeistungComparer.Compare()` – that’s all!

The above in action:

``````// ***** default ascending sort
Leistung yourLeistung = new Leistung( );
Leistung yourLeistung2 = new Leistung( );
List<Leistung> yourList = new List<Leistung>();
// stuff happens, then...
yourList.Sort();

// override
yourList.Sort( new LeistungComparer( SortOrder.descend ) );
``````

Details

``````public enum SortOrder { undefined, ascend, descend }

public class LeistungComparer : Comparer<Leistung>
{
protected int SortBy { get; set; }

/// <summary>
/// Default sort order is ascending
/// </summary>
/// <param name="sortOrder">defaults to ascend</param>
public LeistungComparer( SortOrder sortOrder = SortOrder.ascend )
{
if ( sortOrder == SortOrder.ascend ) SortBy = 1;
if ( sortOrder == SortOrder.descend ) SortBy = -1;
if ( sortOrder == SortOrder.undefined )
throw new NotImplementedException( "Sort Order is undefined" );
}

public override int Compare( Leistung x, Leistung y )
{
int result = SortBy;

if ( x != null && y == null ) return result;
if ( x == null && y != null ) return result * SortBy;
if ( x == null && y == null ) return 0;

result = x.Art.CompareTo( y.Art ) * SortBy;

if ( result == 0 )
result = CompareAngebot( x, y );

return result * SortBy;
}

protected int CompareAngebot( Leistung x, Leistung y )
{
int result = SortBy;
result = x.Angebot.CompareTo( y.Angebot ) * SortBy;

if ( result == 0 )
result = CompareJahr( x, y );

return result;
}

protected int CompareJahr( Leistung x, Leistung y )
{
// you get the idea

return 1;
}
}

public class Leistung : IComparable<Leistung>
{
// properties removed for readability

protected LeistungComparer Comparer { get; set; }

public Leistung (LeistungComparer comparer = null){
Comparer = comparer ?? new LeistungComparer();
}

public int CompareTo( Leistung other )
{
return Comparer.Compare( this, other );
}
}
``````

End Edit

## NOTE: Original answer follows. It has not been modified.

The idomatic way to enable sorting is to implement the `IComparable` interface. And this will definitely simplify the sorting code. So:

``````public class Leistungen : IComparable<Leistungen> {  }
public class Aufzeichnung : IComparable<Aufzeichnung> { }
``````

then you can sort like this:

``````List<Leistungen> myLeistungen;  // pretend we instantiated it too.

myLeistungen.Sort();
``````

And if you want different sort algorithms then create an `IComparer` class for each one as suggested by @ratchetfreak. then you can do the following – which will override your `IComparalble` implementation in the class `Leistungen`:

``````myLeistungen.Sort(myDifferentComparer);
``````

IComparable Implementation

This demonstrates how to compare multiple properties. Both of your classes will implement using this pattern. When `Leistungen.CompareTo()` gets down to comparing its `List<Aufzeichnung>`, well `Aufzeichnung.CompareTo()` takes care of that!

``````public class Leistungen : IComparable<Leistungen> {
\ implementing the generic version means we don't
\ check for or cast to the correct type.
public int CompareTo(Leistungen other) {
int result = 1; // "this" is > "other"

if(other == null) return result;

result = this.Art.CompareTo(other.Art);

if(result == 0)
result = CompareAngebot(other);

return result;
}

protected int CompareAngebot(Leistungen other) {
int result = 1;
result = this.Angebot.CompareTo(other.Angebot);

if(result == 0)
result = CompareJahr(other);

return result;
}

protected int CompareJahr(Leistungen other) { // you get the idea }

// ....

protected int CompareAufzeichnungList(Leistungen other) {
// last property in our compare chain, so it's real simple

return this.Aufzeichnungen.CompareTo(other.Aufzeichnungen);
}

}
``````

One of the improvements you can make is a `foreach` on `sortings` instead of using `.ElementAt(i)` (which will always be slower).

Another improvement would be to convert all those `if` statements in the `else` block to a `switch`.

Third, you should be using `nameof(...)` instead of string constants. This way, if something gets refactored, the name change persists without needing to go through all the strings and look for names to change. (For example, `nameof(Leistung.Angebot)` will return `Angebot`.) Do note: this is C#6.0 only.

Another suggestion is to create a `Comparison<Leistung>` variable to hold your delegate for comparison in. That way, you can create it once and run through each sort as needed. This does require you to create an extra `else if` and duplicate your `for (var j = 0; j ...` loop, but it makes it a bit more maintainable (and likely faster) in the end.

Fifth, I would recommend replacing `for (var j = 0; ...` and `for (var k = 0; ...` with `foreach` loops. They should be faster (if I recall correctly), and you don’t have a need to keep track of `j` or `k` in them.

Another C#6.0 feature you can take advantage of is the `?.` null-condition check to remove the null-check in `Mitarbeiter` sort. `Aufzeichnungen?.Sort` will only call `.Sort` if `Aufzeichnungen` is not null.

Lastly, there’s no need for `string.Equals`. In C# you can directly compare strings with `==`.

All in all, here is the new version (with all the edits I recommend).

Yes, it’s longer, but it’s also more robust, duplicates less, and should likely perform better.

``````internal static IEnumerable<A> Sort(List<A> leistungen, IEnumerable<Sorting> sortings)
{
foreach (var sorting in sortings)
{
var sort = sorting.Ascending ? 1 : -1;

if (sorting.Field == nameof(LaufendeLeistung.Kunde))
{
leistungen.Sort((a, b) => string.Compare(a.Kunde, b.Kunde) * sort);
}
else if (sorting.Field == nameof(Aufzeichnung.Mitarbeiter))
{
Comparison<Aufzeichnung> comparison = (a, b) => string.Compare(a.Mitarbeiter, b.Mitarbeiter) * sort;

foreach (var element in leistungen)
{
foreach (var subElement in element.Leistungen)
{
subElement.Aufzeichnungen?.Sort(comparison);
}
}
}
else
{
Comparison<Leistung> comparison;

switch (sorting.Field)
{
case nameof(Leistung):
comparison = (a, b) => string.Compare(a.Art, b.Art) * sort;
break;
case nameof(Leistung.Angebot):
comparison = (a, b) => string.Compare(a.Angebot, b.Angebot) * sort;
break;
case nameof(Leistung.Jahr):
comparison = (a, b) => string.Compare(a.Jahr, b.Jahr) * sort;
break;
case nameof(Leistung.Berater):
comparison = (a, b) => string.Compare(a.Berater, b.Berater) * sort;
break;
case nameof(Leistung.Assistent):
comparison = (a, b) => string.Compare(a.Assistent, b.Assistent) * sort;
break;
default: // This will perform the same sort as sorting by `Leistung`. The nice thing about this is if the value in `sorting.Field` is an invalid field, it will still sort by *something*.
comparison = (a, b) => string.Compare(a.Art, b.Art) * sort;
break;
}

foreach (var element in leistungen)
{
element.Leistungen.Sort(comparison);
}
}
}

return leistungen;
}
``````

I think that there is some potential for optimization even without rewriting the code completely.

1. By using `sortings.ElementAt(i)` over and over again, you are actually getting the enumerable element every time. As of now, I see no reason not to use `foreach (var sorting in sortings)` and using the `sorting` variable inside the loop, instead of the `for` loop.
2. Depending on how many and which sort fields get passed to the `Sort` method via the `sortings` parameter, you may be re-sorting the same list(s) over and over again. Since List.Sort actually re-sorts the array every time, this not negligible.
3. There is exactly one case where you need to sort the `leistungen` list itself and one where the `Aufzeichnungen` list needs to be sorted. You can identify them before iterating through everything (just use the last entry of the `sortings` list that matches the field name to get the correct sort order) and apply them seperately from the loop.

From an outside perspective, it could also be unexpected that the `leistungen` list is sorted in place and then returned as an `IEnumerable<A>`. I would at least add some documentation that states that the input list will be modified.

A huge downside of your could could be that you depend on `Array.Sort` being called in order to implement the sort with several levels. My suggestion would be to try using the built in LINQ methods instead. By chaining `OrderBy`/`ThenBy` calls, you could avoid running the sort algorithm a lot of times, and instead use the lazy execution of LINQ. Here’s a suggestion on how it could work:

``````public static class Sorter<A> where A : LaufendeLeistung
{
private static readonly IReadOnlyDictionary<string, Func<Leistung, string>> leistungKeySelectors;

static Sorter()
{
var selectors = new Dictionary<string, Func<Leistung, string>>();

selectors.Add("Leistung", l => l.Art);
selectors.Add("Angebot", l => l.Angebot);
selectors.Add("Jahr", l => l.Jahr);
selectors.Add("Berater", l => l.Berater);
selectors.Add("Assistent", l => l.Assistent);

leistungKeySelectors = selectors;
}

internal static IEnumerable<A> Sort(List<A> leistungen, IEnumerable<Sorting> sortings)
{
if (leistungen == null)
{
throw new ArgumentNullException(nameof(leistungen));
}

return sortings == null ? leistungen : SortImpl(leistungen, sortings);
}

private static IEnumerable<A> SortImpl(IEnumerable<A> leistungen, IEnumerable<Sorting> sortings)
{
var customerSorting = sortings.LastOrDefault(s => "Kunde".Equals(s.Field, StringComparison.Ordinal));
var employeeSorting = sortings.LastOrDefault(s => "Mitarbeiter".Equals(s.Field, StringComparison.Ordinal));

if (customerSorting != null)
{
leistungen = leistungen.OrderBy(k => k.Kunde, customerSorting);
}

var leistungenSortings = sortings.Where(s => !"Kunde".Equals(s.Field, StringComparison.Ordinal) && !"Mitarbeiter".Equals(s.Field, StringComparison.Ordinal)).ToList();

foreach (var laufendeLeistung in leistungen)
{
if (laufendeLeistung.Leistungen != null)
{
laufendeLeistung.Leistungen = ProcessLeistungen(laufendeLeistung.Leistungen, leistungenSortings, employeeSorting).ToList();
}

yield return laufendeLeistung;
}
}

private static IEnumerable<Leistung> ProcessLeistungen(IEnumerable<Leistung> leistungen, IEnumerable<Sorting> sortings, Sorting employeeSorting)
{
foreach (var leistung in SortLeistungenByProperties(leistungen, sortings))
{
if (employeeSorting != null && leistung.Aufzeichnungen != null)
{
leistung.Aufzeichnungen = leistung.Aufzeichnungen.OrderBy(a => a.Mitarbeiter, employeeSorting).ToList();
}

yield return leistung;
}
}

private static IEnumerable<Leistung> SortLeistungenByProperties(IEnumerable<Leistung> leistungen, IEnumerable<Sorting> sortings)
{
foreach (var sorting in sortings)
{
// Just an alternative to the switch/case statement.
Func<Leistung, string> selector;
if (leistungKeySelectors.TryGetValue(sorting.Field, out selector))
{
leistungen = leistungen.OrderBy(selector, sorting);
}
}

return leistungen;
}
}

public static class ExtensionMethods
{
public static IOrderedEnumerable<T> OrderBy<T, TKey>(this IEnumerable<T> source, Func<T, TKey> keySelector, Sorting sorting)
{
var result = source as IOrderedEnumerable<T>;
if (result != null)
{

result = sorting.Ascending ? result.ThenBy(keySelector) : result.ThenByDescending(keySelector);
}
else
{
result = sorting.Ascending ? source.OrderBy(keySelector) : source.OrderByDescending(keySelector);
}

return result;
}
}
``````

Note that this assumes that there is actually no need to sort the `List<LaufendeLeistung>` in place, nor should any consumers depend on `Leistungen` or `Aufzeichnungen` not being replaced (there is a public setter after all). There might be slightly higher memory usage etc., because of some allocations (Enumerators, Dictionary, Lists), but it could still be faster with several `sortings`, because of not actually re-sorting the array that backs the List several times. (If this matters, benchmark it. :))

you could define a `IComparer` that holds several `IComparers` and returns the first result that isn’t 0:

``````class CascadedComparer<T> : IComparer<T>{

IList<IComparer<T>> comparings; //fill in constructor

public int Compare(T x, T y){
foreach(var comp in comparings){
int r = comp.compare(x, y);

if(r!=0)
return r;
}
return 0; //all returned 0
}

}
``````

Then you can pass an instance of that filled with the field specific comparers to the `sort` method of `leistungen[j].Leistungen`.

The `Sorting` doesn’t need to hold the string value of the field to compare but instead a Comparer (or a mapping function).

Ortherwise you can build a `map<string, IComparer<A>>` and then you can get the comparer directly from the map.