Code is poetry

Un tri pour IEnumerable<T>

Tout le monde utilise régulièrement la méthode Sort des Lists, ou encore celle des tableaux (Array.Sort). Mais pour une collection très générale, qui n'implémenterait que IEnumerable, il n'existe rien de pratique (je ne parle pas de C# 3.0 bien sur).

Voici un petit tri qui fonctionne avec n'importe quelle collection pourvu qu'elle soit IEnumerable. Cette fonction n'instancie aucune collection, il faudrait utiliser des collections pour atteindre une complexité en O(n * log(n)), ce qui reviendrait à peu de choses près à convertir le IEnumerable en tableau et à trier le tableau.

En tout cas, à défaut d'être efficace, ce code montre une des nombreuses utilisations que l'on peut faire du mot clé yield return. Voici le code :

public static class EnumerableSort
{
    public static IEnumerable<T> Sort<T>(IEnumerable<T> toSort, Comparison<T> comparer)
    {
        IEnumerator<T> enumerator = toSort.GetEnumerator();
        if (!enumerator.MoveNext())
            yield break;

        // Le pivot est enumerator.Current
        foreach (T item in Sort(EnumerateBefore(toSort, comparer, enumerator.Current), comparer))
            yield return item;

        yield return enumerator.Current;

        foreach (T item in Sort(EnumerateAfter(toSort, comparer, enumerator.Current), comparer))
            yield return item; 
    }

    private static IEnumerable<T> EnumerateBefore<T>(IEnumerable<T> toSort, Comparison<T> comparer, T limit)
    {
        foreach (T item in toSort)
            if (comparer(item, limit) < 0)
                yield return item;
    }

    private static IEnumerable<T> EnumerateAfter<T>(IEnumerable<T> toSort, Comparison<T> comparer, T limit)
    {
        foreach (T item in toSort)
            if (comparer(item, limit) > 0)
                yield return item;
    }
}

Attention : cette fonction risque d'oublier des éléments si vous avez plusieurs éléments identiques (mais il faut de toutes petites modifications pour que cela marche). Vous pourrez quand même noter que pour que cela fonctionne, il faut également que la collection s'énumère toujours dans le même ordre.

Il est très facile de transformer cette fonction en extension method de C# 3.0 :

    public static IEnumerable<T> Sort<T>(this IEnumerable<T> toSort, Comparison<T> comparer)

En C# 3.0, vous aurez cependant accès à la méthode d'extension OrderBy qui fait quasiment la même chose.