Wprowadzenie do sortowania w C #
Sortowanie w c # to proces układania zawartości kolekcji w określonej kolejności. Kolekcja może być tablicą, listą lub dowolną inną grupą danych. Kolekcja może zawierać elementy zarówno typów prostych, jak i złożonych. Prostym typem może być zbiór liczb całkowitych, ciągów, liczb zmiennoprzecinkowych itp. Typem złożonym może być zbiór obiektów typów zdefiniowanych przez użytkownika, takich jak Pracownik, Student itp. Typy złożone są częściej niż często zagnieżdżane, co oznacza obiekty mogą mieć wiele atrybutów.
Przykłady
- Prosty typ
- Zbiór liczb całkowitych - (1, 2, 3, 4, 5)
- Kolekcja strun - („Mark”, „Jamie”, „Anna”)
- Typ złożony
- ((Nazwa: „Mark”, identyfikator pracownika: „123”, biuro: „Londyn”),
(Imię i nazwisko: „Jane”, identyfikator pracownika: „456”, biuro: „NY”),
(Nazwisko: „Annie”, identyfikator pracownika: „789”, biuro: „Sydney”))
- ((Nazwa: „Mark”, identyfikator pracownika: „123”, biuro: „Londyn”),
C # zapewnił wbudowane metody sortowania kolekcji. Niezależnie od tego, czy jest to tablica, lista czy jakakolwiek ogólna kolekcja, metoda C # Sort () może posortować ją na podstawie dostarczonego modułu porównującego. Wewnętrznie implementacja .Net używa algorytmu Quicksort do sortowania kolekcji w C #. Więcej na ten temat omówimy w kolejnych sekcjach tego artykułu.
Jak odbywa się sortowanie w C #?
Jak wspomniano wcześniej, środowisko .Net używa metody Quicksort do sortowania elementów w kolekcji C #. Czym jest Quicksort?
Quicksort stosuje strategię dzielenia i podbijania. Oznacza to, że algorytm sortowania wybiera element przestawny i dzieli tablicę na podstawie elementu przestawnego. Elementy mniejsze niż czop są umieszczane przed nim. Elementy większe niż czop są umieszczane za nim. Zapewnia to sortowanie elementu przestawnego. Ponadto tablica jest podzielona na dwa - elementy mniejsze niż oś obrotu i elementy większe niż oś obrotu. Następnie algorytm stosuje to samo podejście dla obu tablic.
Ilustrację tego można zobaczyć poniżej.
Niesortowane tablice - 18, 5, 16, 23, 50, 32
Krok 1 (Pivot = 32) - 18, 5, 16, 23, 32, 50
Krok 2a
Niesortowane tablice - 18, 5, 16, 23
Pivot = 23
Częściowo posortowana tablica - 18, 5, 16, 23
Krok 2b
Niesortowana tablica - 50
Pivot = 50
Częściowo posortowana tablica - 50
Krok 3a
Tablica niesortowana - 18, 5, 16
Pivot = 16
Częściowo posortowana tablica - 5, 16, 18
Sorted Array - 5, 16, 18, 23, 32, 50
W ten sposób Quicksort ma dwa kluczowe procesy - wybór osi przestawnej i partycjonowanie tablicy. Implementacje algorytmu zależą od wyboru osi przestawnej. Może to być pierwszy element, ostatni, dowolny dowolny element lub mediana tablicy. Po zakończeniu partycji i umieszczeniu osi przestawnej we właściwej pozycji algorytm jest rekurencyjnie wywoływany dla tablic podzielonych na partycje, dopóki wszystkie elementy nie zostaną posortowane.
Gdy sortowanie odbywa się w języku C #, pojawia się koncepcja stabilnego i niestabilnego Quicksort. W stabilnym Quicksort, jeśli dwa elementy są równe, ich kolejność z oryginalnej tablicy zostaje zachowana. W przeciwnym razie jest w niestabilnym szybkim segmencie. Implementacja C # wykorzystuje niestabilny Quicksort.
Rodzaje sortowania w C #
W tej części artykułu skupilibyśmy się głównie na dwóch typach kolekcji w C # - tablicach i listach. Zagłębimy się w sposób, w jaki C # sortuje tablice i listy. W następnej części postaram się wyjaśnić to kilkoma przykładami.
1. Sortowanie tablicy w C #
Przyjrzyjmy się różnym sposobom sortowania tablicy w języku C #.
za. Korzystanie z domyślnego modułu porównującego
Jest to domyślna metoda Sort (). Jeśli żadna osoba porównująca nie jest jawnie przekazana do metody, C # używa porządku rosnącego do uporządkowania elementów.
Kod:
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");
)
)
)
Wynik:
b. Korzystanie z niestandardowego programu porównującego
Możemy również dostarczyć własny niestandardowy moduł porównujący do metody Sort (). Poleciłoby to kompilatorowi C # korzystanie z niestandardowego modułu porównującego zamiast domyślnego.
Aby utworzyć niestandardowy moduł porównujący, musimy zaimplementować metodę Compare () z interfejsu IComparer. Poniższy kod pokazuje, jak utworzyć moduł porównujący, który posortowałby elementy w kolejności malejącej.
Stworzyliśmy klasę, odziedziczyliśmy ją z interfejsu IComparer, zaimplementowaliśmy metodę Compare () i zastąpiliśmy ją, aby porównać elementy w kolejności malejącej.
Kod:
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");
)
)
)
Wynik:
do. Korzystanie z par klucz-wartość
C # zapewnia również sposób sortowania jednej tablicy za pomocą wartości klucza z innej tablicy. Poniższy przykład zawiera pary klucz-wartość imion i nazwisk osób. Posortowalibyśmy je według imienia i nazwiska przy użyciu metody Sort ().
Kod:
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));
)
)
)
Wynik:
2. Sortowanie listy w C #
Przyjrzyjmy się różnym sposobom sortowania listy w języku C #.
Uwaga - Aby używać list w języku C #, w tym biblioteki System.Collections.Generic.za. Korzystanie z domyślnego modułu porównującego
Jest to domyślna metoda sort (). jeśli żaden metoda porównawcza nie jest jawnie przekazana do metody, c # używa porządku rosnącego do uporządkowania elementów.
Kod:
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");
)
)
)
Wynik:
b. Korzystanie z niestandardowego programu porównującego
Możemy również zapewnić własny niestandardowy moduł porównujący do metody sort (). Poleciłoby to kompilatorowi c # użycie niestandardowego modułu porównującego zamiast domyślnego.
Aby utworzyć niestandardowy moduł porównujący, musimy zaimplementować metodę Compare () z interfejsu IComparer. Poniższy kod pokazuje, jak utworzyć moduł porównujący, który posortowałby elementy w kolejności malejącej.
Stworzyliśmy klasę, odziedziczyliśmy ją z interfejsu IComparer, zaimplementowaliśmy metodę Compare () i zastąpiliśmy ją, aby porównać elementy w kolejności malejącej.
Kod:
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");
)
)
)
Wynik:
Sortowanie złożonych typów list
Typy list złożonych to listy zdefiniowane przez użytkownika. Mówiąc ściślej, są to listy obiektów klas zdefiniowanych przez użytkownika. Obiekty zdefiniowane przez użytkownika są mieszanką różnych pierwotnych typów. Trudno jest posortować złożony typ listy. Kompilator C # oczekuje, że każda klasa złożona odziedziczy po interfejsie IComparable i zdefiniuje metodę CompareTo (). Ta metoda zawiera instrukcje porównywania elementów listy do sortowania.
W poniższym przykładzie definiujemy zdefiniowaną przez użytkownika klasę pracowników i sortujemy obiekty pracowników na podstawie ich identyfikatorów.
Przykład 1
Kod:
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);
)
)
)
Wynik:
Otóż oczywiste pytanie, które przychodzi mi na myśl, brzmi: co zrobić, jeśli chcemy posortować obiekty klasy pracownika na podstawie innej właściwości? To jest możliwe. Musielibyśmy wdrożyć interfejs IComparer. Spójrzmy na poniższy przykład, aby zrozumieć.
Przykład nr 2
Kod:
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);
)
)
)
Wynik:
Wniosek
W tym artykule szczegółowo omówiono sortowanie kolekcji w języku C #. Skupiliśmy się głównie na tablicach i listach, ponieważ te dwa obejmują również wszystkie pierwotne typy. Gdy koncepcja sortowania w języku C # jest bardzo dobrze zrozumiana, łatwo jest wdrożyć sortowanie w innych kolekcjach, takich jak wyliczenia, słowniki itp. Po zakończeniu tego artykułu zaleca się zapoznanie z dokumentacją MSDN w celu uzyskania dalszych implementacji sortowania w języku C #.
Polecane artykuły
To jest przewodnik po sortowaniu w C #. Tutaj omawiamy wydajność sortowania, rodzaje sortowania, takie jak tablica i lista, wraz z przykładami i implementacją kodu. Możesz także przejrzeć następujące artykuły, aby dowiedzieć się więcej -
- Obiekty w C #
- Dostęp do modyfikatorów w C #
- Sortowanie bąbelkowe w Javie
- Wskaźniki w C #
- Sortowanie w Pythonie
- Tablica ciągów w JavaScript
- Porównywalne w przykładzie Java | Interfejs kolekcji w Javie
- Tablice napisów w C z funkcjami
- Różne przykłady kolekcji w C #