Depois de trabalhar em inúmeros projetos em que vi programadores implementando métodos “alternativos” de ordenação de listas, resolvi escreve um pouco sobre ordenação de listas em .NET.

Que algoritmo utilizar?

Existem diversos algoritmos para ordenação, desde os mais simples “Bubble Sort” até os menos simples e mais eficientes “Quick Sort”.

O .NET Framework implementa como algoritmo de ordenação o “Quick Sort” que se não for o melhor é um dos melhores e mais rápidos existentes.

O “Quick Sort” é um algoritmo não estável de ordenação, com eficiência (no pior caso) de n2. Se comparar-mos ao “Bubble Sort” com eficiência (no pior caso) de 2n2 veremos que o “Quick Sort” é muito mais eficiente.

Observe que (n) representa a quantidade de itens a serem ordenados, ou seja, se tivermos 10 elementos em uma lista, no pior caso nosso algoritmo irá realizar 102 operações para ordenar a lista.

Como funciona a ordenação no .Net?

Como dito anteriormente, o .Net implementa o “Quick Sort” como algoritmo de busca, então, para nós programadores sobra apenas realizar a comparação de A > B, A < B, A = B e assim por diante.

Conceitos de Ordenação Crescente e Decrescente

Primeiramente, precisamos analisar que, se comparar-mos A > B e dissermos que o resultado pode ser (-1 = Menor, 0 = Igual, 1 = Maior) a ordenação será crescente.

Igualmente, se comparar-mos (B > A) e o dissermos que o resultado pode ser (-1 = Menor, 0 = Igual, 1 = Maior) a ordenação será decrescente.

Mas, se os valores finais são iguais, como a ordenação muda?
Simples!

Dizer que B > A é a mesma coisa que dizer que A <= B, portando, ordenamos de forma inversa a original.

Finalmente, a Implementação

Vamos parar de conteúdo técnico – cientifico chato e ir que realmente ao que interessa.
Primeiramente, iremos utilizar um objeto que representa um Usuário:

C#

class User : IComparable
{
    public User() { }

    public User(string name, string cpf, byte age)
    {
        this._Name = name;
        this._CPF = cpf;
        this._Age = age;
    }

    private string _Name;
    private string _CPF;
    private byte _Age;

    public string Name
    {
        get { return _Name; }
        set { _Name = value; }
    }

    public string CPF
    {
        get { return _CPF; }
        set { _CPF = value; }
    }

    public byte Age
    {
        get { return _Age; }
        set { _Age = value; }
    }

    /// <summary>
    /// Comparador Padrão, Compara Nome Ascendente
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    public int CompareTo(User other)
    {
        return this.Name.CompareTo(other.Name);
    }
}

VB.NET

Class User
    Implements IComparable(Of User)

    Public Sub New(ByVal name As String, ByVal cpf As String, ByVal age As Short)
        Me._Name = name
        Me._CPF = cpf
        Me._Age = age
    End Sub

    Private _Name As String
    Private _CPF As String
    Private _Age As Short

    Public ReadOnly Property Name() As String
        Get
            Name = Me._Name
        End Get
    End Property

    Public ReadOnly Property CPF() As String
        Get
            CPF = Me._CPF
        End Get
    End Property

    Public ReadOnly Property Age() As Short
        Get
            Age = Me._Age
        End Get
    End Property

    Public Function CompareTo(ByVal other As User) As Integer Implements System.IComparable(Of User).CompareTo
        Return Me.Name.CompareTo(other.Name)
    End Function
End Class

Temos então um objeto simples que representa um único usuário, em relação à interface “IComparable” e ao método “CompareTo” iremos abordar mais para frente em nosso artigo.
Agora, vamos a implementação de nosso método principal:

C#

static void Main(string[] args)
{
    // Cria Lista de Usuários
    List users = new List();

    // Adiciona os Usuários
    users.Add(new User("Usuário abc", "159.357.456-89", 98));
    users.Add(new User("Usuário ABC", "123.456.789-01", 25));
    users.Add(new User("Usuário XYZ", "987.654.321-98", 40));
    users.Add(new User("Usuário BBB", "456.789.123-85", 18));
    users.Add(new User("Usuário KIO", "123.789.654-35", 36));
    users.Add(new User("Usuário YHG", "369.852.147-88", 58));
    users.Add(new User("Usuário kLf", "012.659.869-12", 98));
    users.Add(new User("Usuário MKL", "589.456.985-74", 86));
    users.Add(new User("Usuário PIU", "229.966.355-11", 75));
    users.Add(new User("Usuário HNJ", "147.963.258-56", 43));
    users.Add(new User("Usuário MeD", "965.874.632-15", 25));
    users.Add(new User("Usuário abc", "357.159.852-46", 68));
    users.Add(new User("Usuário LOP", "326.598.124-57", 98));

    // Orderna por CPF Ascendente
    users.Sort(new UserSort_CPF_ASC());

    // Ordena por CPF Descendente
    users.Sort(new UserSort_CPF_DESC());

    // Ordena por Idade Ascendente
    users.Sort(new UserSort_Age_ASC());

    // Ordena por Idade Descendente
    users.Sort(new UserSort_Age_DESC());

    // Compara por Nome Ascendente (com Comparador Padrão do Objeto User
    users.Sort();

    // Ordena por Idade e Nome Ascendente
    users.Sort(new UserSort_AgeName_ASC());
}

VB.NET

Sub Main()

    ' Cria Lista de Usuários
    Dim users As New List(Of User)

    ' Adiciona os Usuários
    users.Add(New User("Usuário abc", "159.357.456-89", 98))
    users.Add(New User("Usuário ABC", "123.456.789-01", 25))
    users.Add(New User("Usuário XYZ", "987.654.321-98", 40))
    users.Add(New User("Usuário BBB", "456.789.123-85", 18))
    users.Add(New User("Usuário KIO", "123.789.654-35", 36))
    users.Add(New User("Usuário YHG", "369.852.147-88", 58))
    users.Add(New User("Usuário kLf", "012.659.869-12", 98))
    users.Add(New User("Usuário MKL", "589.456.985-74", 86))
    users.Add(New User("Usuário PIU", "229.966.355-11", 75))
    users.Add(New User("Usuário HNJ", "147.963.258-56", 43))
    users.Add(New User("Usuário MeD", "965.874.632-15", 25))
    users.Add(New User("Usuário abc", "357.159.852-46", 68))
    users.Add(New User("Usuário LOP", "326.598.124-57", 98))

    ' Orderna por CPF Ascendente
    users.Sort(New UserSort_CPF_ASC())

    ' Ordena por CPF Descendente
    users.Sort(New UserSort_CPF_DESC())

    ' Ordena por Idade Ascendente
    users.Sort(New UserSort_Age_ASC())

    ' Ordena por Idade Descendente
    users.Sort(New UserSort_Age_DESC())

    ' Compara por Nome Ascendente (com Comparador Padrão do Objeto User
    users.Sort()

    ' Ordena por Idade e Nome Ascendente
    users.Sort(New UserSort_AgeName_ASC())

End Sub

Focaremos na ordenação de listas do tipo (List), mas, o processo é igual em todas as listas (coleções) do .Net que suportam ordenação.

Observemos os métodos (.Sort()) que estamos utilizando.

As listas que suportam ordenação podem ser ordenadas de 2 formas:

1. Ordenação com Comparador Padrão
2. Ordenação com Comparador Customizado

Ordenação com Comparador Padrão

Observemos o código abaixo:

C#

// Compara por Nome Ascendente (com Comparador Padrão do Objeto User
users.Sort();

VB.NET

' Compara por Nome Ascendente (com Comparador Padrão do Objeto User
users.Sort()

Estamos requisitando a ordenação da lista de usuários, mas, com base em que?

Lembremos a interface “IComparable”. Ela indique que o objeto que a implemente suporta comparação com outro objeto igual. Neste caso, o método “CompareTo” deve ser implementado.

Dentro deste método a comparação “padrão” deve ser implementada, no caso do exemplo é uma comparação por Nome de forma Ascendente (A > B).

Ordenação com Comparador Customizado

Pode-se surgir a necessidade de ordenarmos uma coleção com outras métricas como ordenação decrescente ou utilizarmos uma ordenação por vários campos.

C#
/// <summary>
/// Realiza a Comparação por Idade (E caso ocorram repetições compara pelo Nome)
/// </summary>
internal class UserSort_AgeName_ASC : IComparer
{
    public int Compare(User x, User y)
    {
        int value = x.Age.CompareTo(y.Age);

        if (value == 0)
        {
            return x.Name.CompareTo(y.Name);
        }
        else
        {
            return value;
        }
    }
}

/// <summary>
/// Realiza Comparações pela Idade Descendente
/// </summary>
internal class UserSort_Age_DESC : IComparer
{
    public int Compare(User x, User y)
    {
        return y.Age.CompareTo(x.Age);
    }
}

/// <summary>
/// Realiza Comparações pela Idade Ascendente
/// </summary>
internal class UserSort_Age_ASC : IComparer
{
    public int Compare(User x, User y)
    {
        return x.Age.CompareTo(y.Age);
    }
}

/// <summary>
/// Realiza Comparações pelo CPF Descendente
/// </summary>
internal class UserSort_CPF_DESC : IComparer
{
    public int Compare(User x, User y)
    {
        return y.CPF.CompareTo(x.CPF);
    }
}

/// <summary>
/// Realiza Comparações pelo CPF Ascendente
/// </summary>
internal class UserSort_CPF_ASC : IComparer
{
    public int Compare(User x, User y)
    {
        return x.CPF.CompareTo(y.CPF);
    }
}

VB.NET

'''
''' <summary>
''' Realiza a Comparação por Idade (E caso ocorram repetições compara pelo Nome)
''' </summary>
''' <remarks></remarks>
Class UserSort_AgeName_ASC
    Implements IComparer(Of User)

    Public Function Compare(ByVal x As User, ByVal y As User) As Integer Implements System.Collections.Generic.IComparer(Of User).Compare

        Dim value As Int32 = x.Age.CompareTo(y.Age)

        If (value = 0) Then
            Return x.Name.CompareTo(y.Name)
        Else
            Return value
        End If

    End Function
End Class

''' <summary>
''' Realiza Comparações pelo CPF Ascendente
''' </summary>
''' <remarks></remarks>
Class UserSort_CPF_ASC
    Implements IComparer(Of User)

    Public Function Compare(ByVal x As User, ByVal y As User) As Integer Implements System.Collections.Generic.IComparer(Of User).Compare

        Return x.CPF.CompareTo(y.CPF)

    End Function
End Class

''' <summary>
''' Realiza Comparações pelo CPF Descendente
''' </summary>
''' <remarks></remarks>
Class UserSort_CPF_DESC
    Implements IComparer(Of User)

    Public Function Compare(ByVal x As User, ByVal y As User) As Integer Implements System.Collections.Generic.IComparer(Of User).Compare

        Return y.CPF.CompareTo(x.CPF)

    End Function
End Class

''' <summary>
''' Realiza Comparações pela Idade Ascendente
''' </summary>
''' <remarks></remarks>
Class UserSort_Age_ASC
    Implements IComparer(Of User)

    Public Function Compare(ByVal x As User, ByVal y As User) As Integer Implements System.Collections.Generic.IComparer(Of User).Compare

        Return x.Age.CompareTo(y.Age)

    End Function
End Class

''' <summary>
''' Realiza Comparações pela Idade Descendente
''' </summary>
''' <remarks></remarks>
Class UserSort_Age_DESC
    Implements IComparer(Of User)

    Public Function Compare(ByVal x As User, ByVal y As User) As Integer Implements System.Collections.Generic.IComparer(Of User).Compare

        Return y.Age.CompareTo(x.Age)

    End Function
End Class

Eis que temos 5 classes de ordenação que implementam a interface “IComparer” que define a obrigatoriedade para o método “Compare()” que realiza a comparação com 2 objetos do mesmo tipo “<T>”.

1. UserSort_AgeName_ASC – Ordenação por Idade Ascendente e em caso de idade repetida ordena por Nome
2. UserSort_Age_DESC – Ordenação por Idade Decrescente (B > A)
3. UserSort_Age_ASC – Ordenação por Idade Ascendente (A > B)
4. UserSort_CPF_DESC – Ordenação por CPF Decrescente (B > A)
5. UserSort_CPF_ASC – Ordenação por CPF Crescente (A > B)

Com essas classes, podemos executar o código abaixo:

C#

' Orderna por CPF Ascendente
users.Sort(New UserSort_CPF_ASC())

' Ordena por CPF Descendente
users.Sort(New UserSort_CPF_DESC())

' Ordena por Idade Ascendente
users.Sort(New UserSort_Age_ASC())

' Ordena por Idade Descendente
users.Sort(New UserSort_Age_DESC())

' Compara por Nome Ascendente (com Comparador Padrão do Objeto User
users.Sort()

' Ordena por Idade e Nome Ascendente
users.Sort(New UserSort_AgeName_ASC())

Invocando o método (Sort()) com o parâmetro da instância da classe de ordenação (que obrigatoriamente deve implementar IComparer). Desta forma, o algoritmo interno do .Net pode delegar ao método (Compare - da classe customizada do programador) a lógica de ordenação.

Conclusão

Utilizando-se a ordenação padrão do .Net ganhamos em performance (pois o algoritmo utilizado é de excelente performance), produtividade (não precisamos re-inventar a roda) e estabilidade (o algoritmo padrão do .Net já está testado), ficando assim apenas para nós programadores a regra de negócio da ordenação.

Posts Relacionados:

1. Reflection Parte 2 – Construtores
2. Por Dentro das Propriedades Automáticas
3. Tipos Nulos (Nullable Value Types)
4. Reflection – Parte 4 (Propriedades)
5. Reflection – Parte 5 (Interfaces)
6. Calculando CRC de Strings (Texto), Array’s e Arquivos
7. Convertendo Caminhos Absolutos e URL’s Absolutas para Caminhos Relativos e URL’s Relativas