Sorting algorithm

Question

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;
    }

Answer 1

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>();
yourList.Add(yourLeistung);
yourList.Add(yourLeistung2);
// 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);
    }

}

Answer 2

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;
}

Answer 3

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. :))

Answer 4

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.