Sorting in C#

Sorting in c# is the process of arranging the contents of a collection in a specific order. A collection may be an array, a list or any other data group. The collection may contain elements of simple types as well as complex types. A simple type may be a collection of integers, strings, floating-point numbers, etc. A complex type may be a collection of objects of user-defined types such as Employee, Student, etc. Complex types are more than often nested, meaning the objects may have multiple attributes.

Examples

• Simple Type
  • Integer collection – {1, 2, 3, 4, 5}
  • String collection – {“Mark”, “Jamie”, “Anna”}
• Complex Type
  • { [Name: “Mark”, Employee Id: “123”, Office: “London”],
    [Name: “Jane”, Employee Id: “456”, Office: “NY”],
    [Name: “Annie”, Employee Id: “789”, Office: “Sydney”] }

C# has provided in-built methods to sort collections. Be it an Array, List or any Generic Collection, C# Sort() method can sort it based on the Comparer provided. Internally, the .Net implementation uses the Quicksort algorithm to sort collections in C#. We will discuss more on this in subsequent sections of the article.

How Sorting is Performed in C#?

As stated earlier, the .Net framework uses the Quicksort approach to sort the elements in a C# collection. So, what is quicksort?

Quicksort follows a divide and conquer strategy. This means, the sorting algorithm selects a pivot element and divides the array based on the pivot element. The elements smaller than the pivot are placed before it. The elements larger than the pivot are placed after it. This ensures that the pivot element is sorted. Also, the array is divided into two – elements smaller than pivot and elements larger than the pivot. Next, the algorithm follows the same approach for both the arrays.

An illustration of this can be seen below.

Unsorted Array – 18, 5, 16, 23, 50, 32

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

Step 2a
Unsorted Array – 18, 5, 16, 23
Pivot = 23
Partially Sorted Array – 18, 5, 16, 23

Step 2b
Unsorted Array – 50
Pivot = 50
Partially Sorted Array – 50

Step 3a
Unsorted Array – 18, 5, 16
Pivot = 16
Partially Sorted Array – 5, 16, 18

Sorted Array – 5, 16, 18, 23, 32, 50

Thus, Quicksort has two key processes – selecting the pivot and partitioning the array. The implementations of the algorithm depend on the selection of the pivot. It can be either the first element, or the last, or any random element, or the median of the array. Once the partition is done and the pivot is placed in the right position, the algorithm is recursively called for the partitioned arrays, until every element is sorted.

When sorting is done in C#, there comes the concept of stable and unstable Quicksort. In a stable Quicksort, if two elements are equal their order from the original array is preserved. Otherwise, it’s in an unstable quicksort. C# implementation uses unstable Quicksort.

Types of Sorting in C#

In this section of the article, we would be focusing mainly on two types of collections in C# – Arrays and Lists. We would deep dive into how C# sorts the arrays and lists. The next section would try to explain it with some examples.

1. Sorting an Array in C#

Let us look at the different ways in which we can sort an array in C#.

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:

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");
}
}
}

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;
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");
}
}
}

Output:

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 
<p><strong>Output:</strong></p>
<p><img  src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172534825553136.png?x-oss-process=image/resize,p_40" class="lazy" alt="Sorting in C#" ></p>
<h4 id="Sorting-a-List-in-C">2. Sorting a List in C#</h4>
<p>Let us look at the different ways in which we can sort a list in C#.</p>
<strong>Note</strong> – To use Lists in C#, including the library System.Collections.Generic.
<h5 id="a-Using-Default-Comparer">a. Using Default Comparer</h5>
<p>This is the default sort() method. if no comparer is explicitly passed to the method, c# uses the ascending order to arrange the elements.</p>
<p><b>Code:</b></p>
<pre class="brush:php;toolbar:false">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");
}
}
}</int></string></int></int></string></string>

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");
}
}
}</int></string></int></int></string></string></int></string>

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);
}
}
}</employee></employee></employee></employee>

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);
}
}
}</employee></employee></employee></employee></employee>

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#.

The above is the detailed content of Sorting in C#. For more information, please follow other related articles on the PHP Chinese website!