Introduction au 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 plus souvent imbriqués, ce qui signifie les objets peuvent avoir plusieurs attributs.
Exemples
- Type simple
- Collection entière - (1, 2, 3, 4, 5)
- Collection de cordes - («Mark», «Jamie», «Anna»)
- Type complexe
- ((Nom: "Mark", numéro d'employé: "123", bureau: "Londres"),
(Nom: «Jane», numéro d'employé: «456», bureau: «NY»),
(Nom: «Annie», numéro d'employé: «789», bureau: «Sydney»))
- ((Nom: "Mark", numéro d'employé: "123", bureau: "Londres"),
C # a fourni des méthodes intégrées pour trier les collections. Que ce soit un tableau, une liste ou toute collection générique, la méthode C # Sort () peut le trier en fonction du Comparer fourni. En interne, l'implémentation .Net utilise l'algorithme Quicksort pour trier les collections en C #. Nous en discuterons plus en détail 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 de division et de conquête. 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é. De plus, le tableau est divisé en deux éléments - plus petits que pivot et éléments plus grands que pivot. Ensuite, l'algorithme suit la même approche pour les deux tableaux.
Une illustration de ceci peut être vue ci-dessous.
Réseau non trié - 18, 5, 16, 23, 50, 32
Étape 1 (pivot = 32) - 18, 5, 16, 23, 32, 50
Étape 2a
Réseau non trié - 18, 5, 16, 23
Pivot = 23
Réseau partiellement trié - 18, 5, 16, 23
Étape 2b
Réseau non trié - 50
Pivot = 50
Réseau partiellement trié - 50
Étape 3a
Réseau non trié - 18, 5, 16
Pivot = 16
Réseau partiellement trié - 5, 16, 18
Tableau trié - 5, 16, 18, 23, 32, 50
Ainsi, Quicksort a deux processus clés - sélection du pivot et partitionnement de la baie. 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 tout é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 récursivement appelé pour les tableaux partitionnés, jusqu'à ce que chaque élément soit trié.
Lorsque le tri est effectué en C #, vient le concept de Quicksort stable et instable. Dans un Quicksort stable, si deux éléments sont égaux, leur ordre à partir du tableau d'origine est préservé. Sinon, c'est dans un tri rapide instable. L'implémentation C # utilise Quicksort instable.
Types de tri en C #
Dans cette section de l'article, nous nous concentrerions principalement sur deux types de collections en C # - Tableaux et listes. Nous approfondirions la façon dont C # trie les tableaux et les listes. La section suivante essaiera de l'expliquer avec quelques exemples.
1. Tri d'un tableau en C #
Examinons les différentes façons dont nous pouvons trier un tableau en C #.
une. Utiliser Default Comparer
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");
)
)
)
Production:
b. Utilisation de Comparer personnalisé
Nous pouvons également fournir notre propre Comparer 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 dans l'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 surchargée pour comparer les éléments dans l'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");
)
)
)
Production:
c. Utilisation de paires de valeurs-clés
C # fournit également un moyen de trier un tableau à l'aide des valeurs de clé d'un autre tableau. L'exemple ci-dessous présente des paires clé-valeur de prénoms et de noms de personnes. Nous les trierions par prénom et par nom en utilisant la méthode Sort ().
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));
)
)
)
Production:
2. Tri d'une liste en C #
Examinons les différentes manières dont nous pouvons trier une liste en C #.
Remarque - Pour utiliser les listes en C #, y compris la bibliothèque System.Collections.Generic.une. Utiliser Default Comparer
Il s'agit de la méthode sort () par défaut. si aucun comparateur n'est explicitement passé à la méthode, c # utilise l'ordre croissant pour organiser les éléments.
Code:
public class Program
using System.Collections.Generic;
(
public static void Main()
(
String() strArray = ("I", "Am", "Learning", "Array", "Sorting", "In", "C#");
List strList = new List(strArray);
int() intArray = (23, 76, 12, 43, 90, 30);
List intList = new List(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 myList)
(
foreach (string a in myList)
(
Console.Write(a + "\t");
)
)
static void DisplayList(List myList)
(
foreach (int a in myList)
(
Console.Write(a + "\t");
)
)
)
Production:
b. Utilisation de Comparer 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 dans l'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 surchargée pour comparer les éléments dans l'ordre décroissant.
Code:
using System;
using System.Collections.Generic;
public class LengthComparer : IComparer
(
public int Compare(string a, string b)
(
return (a.Length.CompareTo(b.Length));
)
)
public class DigitSumComparer : IComparer
(
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 strList = new List(strArray);
int() intArray = (23, 76, 12, 43, 90, 30);
List intList = new List(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 myList)
(
foreach (string a in myList)
(
Console.Write(a + "\t");
)
)
static void DisplayList(List myList)
(
foreach (int a in myList)
(
Console.Write(a + "\t");
)
)
)
Production:
Tri des types de liste complexes
Les types de listes complexes sont des listes définies par l'utilisateur. Pour être plus précis, ce sont des listes d'objets de classes définies par l'utilisateur. Étant définis par l'utilisateur, les objets sont un mélange de divers types primitifs. Il est difficile de trier un type de liste complexe. Le compilateur C # attend que chaque classe complexe hérite de l'interface IComparable et définisse la méthode CompareTo (). Cette méthode contient les instructions sur la façon de comparer les éléments de la liste pour le tri.
Dans l'exemple ci-dessous, nous définissons une classe d'employés définie par l'utilisateur et trions les objets Employé en fonction de leurs ID.
Exemple 1
Code:
using System;
using System.Collections.Generic;
public class Employee : IComparable
(
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 emps = new List();
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 emp)
(
foreach (Employee e in emp)
(
Console.WriteLine("Id: " + e.id + ", Name: " + e.name + ", Salary: " + e.salary);
)
)
)
Production:
Maintenant, la question évidente qui vient à l'esprit est que si nous voulons trier les objets de la classe Employee en fonction d'une autre propriété? C'est possible. Nous aurions besoin de mettre en œuvre l'interface IComparer. Jetons un coup d'œil à l'exemple ci-dessous pour comprendre.
Exemple # 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
(
public int Compare(Employee e1, Employee e2)
(
return e1.name.CompareTo(e2.name);
)
)
public class SortBySalary : IComparer
(
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 emps = new List();
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 emp)
(
foreach (Employee e in emp)
(
Console.WriteLine("Id: " + e.id + ", Name: " + e.name + ", Salary: " + e.salary);
)
)
)
Production:
Conclusion
Donc, cet article a couvert en détail la façon de trier les collections en C #. Nous nous sommes concentrés principalement sur les tableaux et les listes, car ces deux couvrent également tous les types primitifs. Une fois que le concept de tri en C # est très bien compris, il devient facile d'implémenter le tri dans d'autres collections telles que les énumérations, les dictionnaires, etc. Après avoir terminé cet article, il est recommandé d'explorer la documentation MSDN pour plus d'implémentations du tri en C #.
Articles recommandés
Ceci est un guide de tri en C #. Nous discutons ici des performances de tri, des types de tri tels que tableau et liste, ainsi que des exemples et de l'implémentation de code. Vous pouvez également consulter les articles suivants pour en savoir plus -
- Objets en C #
- Modificateurs d'accès en C #
- Tri des bulles en Java
- Pointeurs en C #
- Tri en Python
- Tableau de chaînes en JavaScript
- Comparable en Java Exemple | Interface de collecte en Java
- Tableau de chaînes en C avec fonctions
- Différents exemples de collections en C #