O sortowaniu kolekcji typów generycznych słów kilka

Dzisiaj zaprezentuję dostępne na platformie .NET mechanizmy służące do sortowania kolekcji typów generycznych. Jako przykładowej kolekcji użyjemy klasy List<T>.

Na początek weźmy pod lupę metodę Sort() klasy List<T> oraz jej przeciążone wersje:

1. Bezparametrowa Sort() – do sortowania wykorzystuje interfejs IComparable<T>
2. Sort(IComparer<T> comparer) – wykorzystująca interfejs IComparer<T>
3. Sort(int index, int count, IComparer<T> comparer) – jak poprzednia, ale pozwala sortować wybrane fragmenty listy.
4. Sort(Comparison<T> comparison) – używająca mechanizmu delegacji

Dla przykładu użyjemy klasy zawierającej informacje o filmie:

public class Movie
{
    private int _id;
    private string _title;
    private string _director;
    private int _year;
    private string _genre;

    public int ID
    {
        get { return _id; }
        set { _id = value; }
    }

    public string Title
    {
        get { return _title; }
        set { _title = value; }
    }

    public string Director
    {
        get { return _director; }
        set { _director = value; }
    }

    public string Genre
    {
        get { return _genre; }
        set { _genre = value; }
    }

    public int Year
    {
        get { return _year; }
        set { _year = value; }
    }

    public Movie(int id, string title, string director, string genre, int year)
    {
        _id = id;
        _title = title;
        _director = director;
        _genre = genre;
        _year = year;
    }

    public override string ToString()
    {
        return string.Format("ID: {0}, Name: {1}, Director: {2}, Genre: {3}, Year: {4}", _id, _title, _director, _genre, _year);
    }
}

Utworzymy również kolekcję filmów:

var movies = new List();
movies.Add(new Movie(1, "Szeregowiec Ryan", "Steven Spielberg", "Dramat", 1998));
movies.Add(new Movie(2, "Patriota", "Roland Emmerich", "Akcja", 2000));
movies.Add(new Movie(3, "Forest Gump", "Robert Zemeckis", "Komedia", 1994));
movies.Add(new Movie(4, "Regulamin zabijania", "William Friedkin", "Thriller", 2000))

Teraz w celu posortowania kolekcji wywołamy metodę Sort() bez żadnych parametrów:

movies.Sort();

Niestety po uruchomieniu programu otrzymamy informację o wystąpieniu wyjątku InvalidOperationException z komunikatem: „Failed to compare two elements in the array”. Wyjątek ten został zgłoszony, ponieważ nasza klasa nie implementuje interfejsu IComparable, wymaganego przez metodę Sort(). Przez to kompilator nie ma pojęcia, w jaki sposób (po których polach) ma posortować nasze obiekty. Aby kolekcja obiektów naszej klasy dała się posortować, musimy samodzielnie zaimplementować interfejs IComparable. Wszystkie typy proste np. int i string mają wbudowaną implementację tego interfejsu. Należy on do przestrzeni nazw System a jego jedyną składową jest metoda CompareTo():

public int CompareTo(Movie other)

Metoda ta zwraca wartość typu int według poniższego schematu:

Obiekt w nawiasie (other) jest porównywany z bieżącym obiektem klasy (this) implementującej metodę CompareTo(). Zwracana wartość całkowita reprezentuje wynik porównania. Poniżej zmiany, które należy wprowadzić do naszej klasy:

public class Movie : IComparable<Movie>
{
    [...]
    public int CompareTo(Movie other)
    {
        if (this.ID > other.ID)
            return 1;
        else if (this.ID < other.ID)
            return -1;
        else
            return 0;
    }
    [...]
}

Po zaimplementowaniu interfejsu możemy już wykorzystywać bezparametrową metodę Sort naszej listy.

movies.Sort();

Pokazane rozwiązanie umożliwia nam sortowanie elementów według wartości wybranego na stałe wcześniej pola. Aby zmienić sposób sortowania, należy dokonać zmiany w kodzie metody CompareTo, uwzględniając nowe pole, po którym będzie sortowali. Następnie ponownie skompilujemy program, aby zmiany zostały uwzględnione.

Bardziej realistyczne i elastyczne podejście pozwoli nam na sortowanie elementów według wielu pól. W tym celu możemy wykorzystać interfejs IComparer do utworzenia klas porównujących dwa obiekty naszej klasy lub delegację Comparison<T>.

Interfejs IComparer należy do przestrzeni nazw System.Collections.Generic. Przypomina trochę interfejs IComparable. Również udostępnia tylko jedną składową, ale za to dwuargumentową metodę Compare(). Metoda ta zwraca wartość -1, 0 lub 1 w zależności od tego, czy pierwszy obiekt jest odpowiednio mniejszy, równy lub większy od drugiego. Składnia tej metody jest następująca:

public int Compare(Movie x, Movie y)

Sortowanie kolekcji za pomocą interfejsu IComparer wymaga od nas utworzenia odrębnej klasy, która po tym interfejsie będzie dziedziczyła:

public class MovieCompareByTitle : IComparer<Movie>
{
    public int Compare(Movie x, Movie y)
    {
        return string.Compare(x.Title, y.Title);
    }
}

Wywołanie metody sort:

movies.Sort(new MovieCompareByTitle());

lub

movies.Sort(2, 2, new MovieCompareByTitle());

Drugi sposób posortuje tylko 2 kolejne elementy naszej listy począwszy od elementu trzeciego.

Analogicznie możemy utworzyć klasy do sortowania po pozostałych polach klasy Movie. Ich kod jest dostępny w przykładowej aplikacji.

Pozostał już tylko do omówienia ostatni sposób sortowania, który wykorzystuje mechanizm delegacji, mianowicie: Comparison<T>. Reprezentuje on metodę, która porównuje dwa obiekty tego samego typu, a jej składnia wygląda następująco:

public delegate int Comparison<in T>(T x, T y)

Do posortowania możemy wykorzystać:

1. metodę anonimową, gdzie treść umieszczana jest bezpośrednio w wywołaniu innej metody

movies.Sort(delegate(Movie x, Movie y)
            {
                return x.Genre.CompareTo(y.Genre);
            });

2. metodę zdefiniowaną w innym miejscu naszego kodu

movies.Sort(CompareByDirector);

[...]
private static int CompareByDirector(Movie x, Movie y)
{
    return x.Director.CompareTo(y.Director);
}
[...]

3. metodę anonimową, gdzie delegacja umieszczona jest bezpośrednio w kodzie naszej klasy Movie

public class Movie : IComparable<Movie>
{
    [...]
    public static Comparison<Movie> TitleComparison =
                                        delegate(Movie x, Movie y)
                                        {
                                            return x.Title.CompareTo(y.Title);
                                        };
    [...]
}

[...]
movies.Sort(Movie.TitleComparison);
[...]

4. metodę utworzoną w ciele klasy Movie o sygnaturze odpowiadajcej delegacji Comparision<T>:

public class Movie : IComparable<Movie>
{
    [...]
    public static int DirectorComparison(Movie x, Movie y)
    {
        return x.Director.CompareTo(y.Director);
    }
    [...]
}

[...]
movies.Sort(Movie.DirectorComparison);
[...]

Warto zauważyć, że dwie ostatnie metody (klasy Movie) nie odwołują się do żadnych składowych obiektu, więc można je zadeklarować jako statyczne.

Platforma .NET oddaje w nasze ręce kilka mechanizmów umożliwiających sortowanie naszych własnych klas. To, który sposób wybierzemy, zależy już od tylko nas i specyfiki projektu, nad którym aktualnie pracujemy.

Przykładowy kod zamieszczam do pobrania poniżej.

Sortowanie
Sortowanie.zip

Przykłady sortowania kolekcji typów generycznych za pomocą mechanizmów dostępnych na platformie .NET.

Autor:	Marcin Kozub
Platformy:	Windows XP, Windows Vista, Windows 7
Kategoria:	Pliki źródłowe
Licencja:	Freeware
Data:	20 marca 2012

23.3 KiB
Pobrano 194 razy
Szczegóły...