Desenvolvimento - C#
.Net Framework Inside : Ordenação de Listas
Depois de trabalhar em inúmeros projetos em que vi programadores implementando métodos “alternativos” de ordenação de listas, resolvi escrever um pouco sobre ordenação de listas em .NET.
por Guilherme Bacellar MoralezDepois de trabalhar em inúmeros projetos em que vi programadores implementando métodos “alternativos” de ordenação de listas, resolvi escrever 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<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 a 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:
- " 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<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 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.
