Tri en C#

Le tri en c# est le processus d'organisation du contenu d'une collection dans un ordre spécifique. Une collection peut être un tableau, une liste ou tout autre groupe de données. La collection peut contenir des éléments de types simples ainsi que des types complexes. Un type simple peut être une collection d'entiers, de chaînes, de nombres à virgule flottante, etc. Un type complexe peut être une collection d'objets de types définis par l'utilisateur tels que Employé, Étudiant, etc. Les types complexes sont le plus souvent imbriqués, ce qui signifie les objets peuvent avoir plusieurs attributs.

Exemples

• Type simple
  • Collection d'entiers – {1, 2, 3, 4, 5}
  • Collection de cordes – {« Mark », « Jamie », « Anna »>
• Type complexe
  • { [Nom : « Mark », ID d'employé : « 123 », Bureau : « Londres »],
    [Nom : « Jane », ID d'employé : « 456 », Bureau : « NY »],
    [Nom : « Annie », ID d'employé : « 789 », Bureau : « Sydney »] >

C# a fourni des méthodes intégrées pour trier les collections. Qu'il s'agisse d'un tableau, d'une liste ou de toute collection générique, la méthode C# Sort() peut le trier en fonction du comparateur fourni. En interne, l'implémentation .Net utilise l'algorithme Quicksort pour trier les collections en C#. Nous en discuterons davantage dans les sections suivantes de l'article.

Comment le tri est effectué en C# ?

Comme indiqué précédemment, le framework .Net utilise l'approche Quicksort pour trier les éléments d'une collection C#. Alors, qu’est-ce que le tri rapide ?

Quicksort suit une stratégie diviser pour mieux régner. Cela signifie que l'algorithme de tri sélectionne un élément pivot et divise le tableau en fonction de l'élément pivot. Les éléments plus petits que le pivot sont placés devant lui. Les éléments plus grands que le pivot sont placés après celui-ci. Cela garantit que l’élément pivot est trié. En outre, le tableau est divisé en deux : des éléments plus petits que le pivot et des éléments plus grands que le pivot. Ensuite, l'algorithme suit la même approche pour les deux tableaux.

Une illustration de ceci peut être vue ci-dessous.

Tableau non trié – 18, 5, 16, 23, 50, 32

Étape 1 (Pivot = 32) – 18, 5, 16, 23, 32, 50

Étape 2a
Tableau non trié – 18, 5, 16, 23
Pivot = 23
Tableau partiellement trié – 18, 5, 16, 23

Étape 2b
Tableau non trié – 50
Pivot = 50
Tableau partiellement trié – 50

Étape 3a
Tableau non trié – 18, 5, 16
Pivot = 16
Tableau partiellement trié – 5, 16, 18

Tableau trié – 5, 16, 18, 23, 32, 50

Ainsi, Quicksort comporte deux processus clés : la sélection du pivot et le partitionnement du tableau. Les implémentations de l'algorithme dépendent de la sélection du pivot. Il peut s'agir soit du premier élément, soit du dernier, soit de n'importe quel élément aléatoire, soit de la médiane du tableau. Une fois la partition terminée et le pivot placé dans la bonne position, l'algorithme est appelé récursivement pour les tableaux partitionnés, jusqu'à ce que chaque élément soit trié.

Lorsque le tri est effectué en C#, apparaît le concept de tri rapide stable et instable. Dans un tri rapide stable, si deux éléments sont égaux, leur ordre par rapport au tableau d'origine est conservé. Sinon, le tri rapide est instable. L'implémentation C# utilise un tri rapide instable.

Types de tri en C#

Dans cette section de l'article, nous nous concentrerions principalement sur deux types de collections en C# : les tableaux et les listes. Nous approfondirons la façon dont C# trie les tableaux et les listes. La section suivante tenterait de l'expliquer avec quelques exemples.

1. Tri d'un tableau en C#

Regardons les différentes manières dont nous pouvons trier un tableau en C#.

a. Utilisation du comparateur par défaut

Il s'agit de la méthode Sort() par défaut. Si aucun Comparer n'est explicitement transmis à la méthode, C# utilise l'ordre croissant pour organiser les éléments.

Code :

using System;
public class Program
{
public static void Main()
{
String[] strArray = {"I", "Am", "Learning", "Array", "Sorting","In", "C#"};
int[] intArray = {23, 76, 12, 43, 90, 30};
Array.Sort(strArray);
Array.Sort(intArray);
Console.WriteLine("Sorted String Array:\n");
DisplayArray(strArray);
Console.WriteLine("\n\n\nSorted Integer Array:\n");
DisplayArray(intArray);
}
static void DisplayArray(string[] arr)
{
foreach (string a in arr)
{
Console.Write(a + "\t");
}
}
static void DisplayArray(int[] arr)
{
foreach (int a in arr)
{
Console.Write(a + "\t");
}
}
}

Sortie :

b. Utiliser un comparateur personnalisé

Nous pouvons également fournir notre propre comparateur personnalisé à la méthode Sort(). Cela demanderait au compilateur C# d'utiliser le comparateur personnalisé au lieu de celui par défaut.

Pour créer un comparateur personnalisé, nous devons implémenter la méthode Compare() à partir de l'interface IComparer. Le code ci-dessous montre comment créer un comparateur qui trierait les éléments par ordre décroissant.

Nous avons créé une classe, l'avons héritée de l'interface IComparer, implémenté la méthode Compare() et l'avons remplacée pour comparer les éléments par ordre décroissant.

Code :

using System;
public class DescendingComparer : System.Collections.IComparer
{
public int Compare(Object a, Object b)
{
return (new System.Collections.CaseInsensitiveComparer()).Compare(b, a);
}
}
public class Program
{
public static void Main()
{
String[] strArray = {"I", "Am", "Learning", "Array", "Sorting","In", "C#"};
int[] intArray = {23, 76, 12, 43, 90, 30};
Array.Sort(strArray, new DescendingComparer());
Array.Sort(intArray, new DescendingComparer());
Console.WriteLine("Sorted String Array in Descending Order:\n");
DisplayArray(strArray);
Console.WriteLine("\n\n\nSorted Integer Array in Desc Order:\n");
DisplayArray(intArray);
}
static void DisplayArray(string[] arr)
{
foreach (string a in arr)
{
Console.Write(a + "\t");
}
}
static void DisplayArray(int[] arr)
{
foreach (int a in arr)
{
Console.Write(a + "\t");
}
}
}

Sortie :

c. Using Key-Value Pairs

C# also provides a way to sort one array using key values from another array. The example below has key-value pairs of first names and last names of people. We would sort them by both first and last names using the Sort() method.

Code:

using System;
public class Program
{
public static void Main()
{
String[] firstNames = {"Tom", "Jack", "Anna", "Veronica", "Jessica", "Mike"};
String[] lastNames = {"Phelps", "Anderson", "Spectre", "Clarke",   "Williams", "Fonseca"};
Array.Sort(firstNames, lastNames);
Console.WriteLine("Sorted by First Names:\n");
DisplayArray(firstNames, lastNames);
Array.Sort(lastNames, firstNames);
Console.WriteLine("\n\nSorted by Last Names:\n");
DisplayArray(firstNames, lastNames);
}
static void DisplayArray(string[] arr1, string[] arr2)
{
for (int i = 0; i < arr1.Length; i++)
{
Console.WriteLine(arr1[i] + " " + arr2[i]);
}
}
}

Output:

2. Sorting a List in C#

Let us look at the different ways in which we can sort a list in C#.

Note – To use Lists in C#, including the library System.Collections.Generic.

a. Using Default Comparer

This is the default sort() method. if no comparer is explicitly passed to the method, c# uses the ascending order to arrange the elements.

Code:

public class Program
using System.Collections.Generic;
{
public static void Main()
{
String[] strArray = {"I", "Am", "Learning", "Array", "Sorting", "In", "C#"};
List<string> strList = new List<string>(strArray);
int[] intArray = {23, 76, 12, 43, 90, 30};
List<int> intList = new List<int>(intArray);
strList.Sort();
intList.Sort();
Console.WriteLine("Sorted String List:\n");
DisplayList(strList);
Console.WriteLine("\n\n\nSorted Integer List:\n");
DisplayList(intList);
}
static void DisplayList(List<string> myList)
{
foreach (string a in myList)
{
Console.Write(a + "\t");
}
}
static void DisplayList(List<int> myList)
{
foreach (int a in myList)
{
Console.Write(a + "\t");
}
}
}

Output:

b. Using Custom Comparer

We can also provide our own custom comparer to the sort() method. This would instruct the c# compiler to use the custom comparer instead of the default one.

To create a custom comparer, we need to implement the Compare() method from the IComparer interface. The code below demonstrates how to create a comparer that would sort the elements in descending order.

We created a class, inherited it from the IComparer interface, implemented the Compare() method and overrode it to compare the elements in descending order.

Code:

using System;
using System.Collections.Generic;
public class LengthComparer : IComparer<string>
{
public int Compare(string a, string b)
{
return (a.Length.CompareTo(b.Length));
}
}
public class DigitSumComparer : IComparer<int>
{
public int Compare(int a, int b)
{
int sum_a = 0;
int sum_b = 0;
while (a > 0)
{
sum_a += (a % 10);
a /= 10;
}
while (b > 0)
{
sum_b += (b % 10);
b /= 10;
}
return (sum_a.CompareTo(sum_b));
}
}
public class Program
{
public static void Main()
{
LengthComparer lc = new LengthComparer();
DigitSumComparer dsc = new DigitSumComparer();
String[] strArray = {"I", "Am", "Learning", "Array", "Sorting", "In", "C#"};
List<string> strList = new List<string>(strArray);
int[] intArray = {23, 76, 12, 43, 90, 30};
List<int> intList = new List<int>(intArray);
strList.Sort(lc);
intList.Sort(dsc);
Console.WriteLine("Sorted String List by Length:\n");
DisplayList(strList);
Console.WriteLine("\n\n\nSorted Integer List by Sum of Digits:\n");
DisplayList(intList);
}
static void DisplayList(List<string> myList)
{
foreach (string a in myList)
{
Console.Write(a + "\t");
}
}
static void DisplayList(List<int> myList)
{
foreach (int a in myList)
{
Console.Write(a + "\t");
}
}
}

Output:

Sorting Complex List Types

Complex List Types are user-defined lists. To be more precise, they are lists of objects of user-defined classes. Being user-defined, the objects are a mixture of various primitive types. It is difficult to sort a complex list type. C# compiler expects each complex class to inherit from the IComparable interface and define the method CompareTo(). This method contains the instructions on how to compare the elements of the list for sorting.

In the example below, we define a user-defined class of Employees and sort the Employee objects based on their IDs.

Example #1

Code:

using System;
using System.Collections.Generic;
public class Employee : IComparable<Employee>
{
public int id {get;set;}
public string name{get;set;}
public double salary{get;set;}
public int CompareTo(Employee e)
{
return this.id.CompareTo(e.id);
}
}
public class Program
{
public static void Main()
{
List<Employee> emps = new List<Employee>();
emps.Add(new Employee()
{id = 123, name = "Tom Phelps", salary = 20000.00});
emps.Add(new Employee()
{id = 897, name = "Jack Anderson", salary = 40050.50});
emps.Add(new Employee()
{id = 342, name = "Anna Spectre", salary = 31030.89});
emps.Add(new Employee()
{id = 219, name = "Veronica Clarke", salary = 66333.66});
emps.Add(new Employee()
{id = 642, name = "Jessica Williams", salary = 50505.05});
emps.Add(new Employee()
{id = 923, name = "Mike Fonseca", salary = 76543.21});
Console.WriteLine("Original Employee List:\n");
DisplayList(emps);
emps.Sort();
Console.WriteLine("\n\nSorted Employee List by IDs:\n");
DisplayList(emps);
}
static void DisplayList(List<Employee> emp)
{
foreach (Employee e in emp)
{
Console.WriteLine("Id: " + e.id + ", Name: " + e.name + ",  Salary: " + e.salary);
}
}
}

Output:

 

Now, the obvious question that comes to mind is that what if we want to sort the objects of Employee class based on some other property? This is possible. We would need to implement the IComparer interface. Let us take a look at the example below to understand.

Example #2

Code:

using System;
using System.Collections.Generic;
public class Employee
{
public int id {get;set;}
public string name{get;set;}
public double salary{get;set;}
}
public class SortByName : IComparer<Employee>
{
public int Compare(Employee e1, Employee e2)
{
return e1.name.CompareTo(e2.name);
}
}
public class SortBySalary : IComparer<Employee>
{
public int Compare(Employee e1, Employee e2)
{
return e1.salary.CompareTo(e2.salary);
}
}
public class Program
{
public static void Main()
{
SortByName sbn = new SortByName();
SortBySalary sbs = new SortBySalary();
List<Employee> emps = new List<Employee>();
emps.Add(new Employee()
{id = 123, name = "Tom Phelps", salary = 20000.00});
emps.Add(new Employee()
{id = 897, name = "Jack Anderson", salary = 40050.50});
emps.Add(new Employee()
{id = 342, name = "Anna Spectre", salary = 31030.89});
emps.Add(new Employee()
{id = 219, name = "Veronica Clarke", salary = 66333.66});
emps.Add(new Employee()
{id = 642, name = "Jessica Williams", salary = 50505.05});
emps.Add(new Employee()
{id = 923, name = "Mike Fonseca", salary = 76543.21});
emps.Sort(sbn);
Console.WriteLine("Sorted Employee List by Names:\n");
DisplayList(emps);
emps.Sort(sbs);
Console.WriteLine("\n\nSorted Employee List by Salaries:\n");
DisplayList(emps);
}
static void DisplayList(List<Employee> emp)
{
foreach (Employee e in emp)
{
Console.WriteLine("Id: " + e.id + ", Name: " + e.name + ",  Salary: " + e.salary);
}
}
}

Output:

Conclusion

So, this article covered in-depth on how to sort collections in C#. We focused majorly on Arrays and Lists since these two covers all the primitive types as well. Once the concept of Sorting in C# is very well understood, it becomes easy to implement sorting in other collections such as Enumerations, Dictionaries, etc. After completing this article, it is recommended to explore the MSDN documentation for more implementations of Sorting in C#.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!