Portal iMastersPortal iMasters
Assine a newsletterNewsletter
Dev (Back & Front)ARTIGO

.Net Framework Inside: Ordenação de Listas

Guilherme BacellarAutor
10 de outubro de 2008 às 10:00
8 min de leitura

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 compararmos 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 compararmos A > B e dissermos que o resultado pode ser (-1 = Menor, 0 = Igual, 1 = Maior) a ordenação será crescente.

Igualmente, se compararmos (B > A) e 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 à original.

Finalmente, a Implementação

Vamos parar de conteúdo técnico – científico chato e ir que realmente ao que interessa.

Primeiramente, iremos utilizar um objeto que representa um Usuário:

C#

class User : IComparable<User>
{
   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 à implementação de nosso método principal:

C#

static void Main(string[] args)
{
   // Cria Lista de Usuários
   List<User> users = new List<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());
}

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<T>), mas o processo é igual em todas as listas 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:

  • Ordenação com Comparador Padrão
  • 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 quê?

Lembremos a interface “IComparable”. Ela indica 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<User>
{
   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<User>
{
   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<User>
{
   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<User>
{
   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<User>
{
   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>“.

  • UserSort_AgeName_ASC – Ordenação por Idade Ascendente e em caso de idade repetida ordena por Nome
  • UserSort_Age_DESC – Ordenação por Idade Decrescente (B > A)
  • UserSort_Age_ASC – Ordenação por Idade Ascendente (A > B)
  • UserSort_CPF_DESC – Ordenação por CPF Decrescente (B > A)
  • 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());
            
// Ordena por Idade e Nome Ascendente
users.Sort(new UserSort_AgeName_ASC());

VB.NET

' 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 reinventar 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.

Guilherme BacellarAutor

é Bacharel em Ciências da Computação, Desenvolvedor .NET há 6 anos, MCAD, Autor de Livros e Artigos, Engenheiro de Segurança de Internet Banking e membro da Kontrolu. WebSite: http://www.kontrolu.com.br

mail
Ver perfil →

Mais de Guilherme Bacellar

↳

Fios