C# - Sort Examples - Dot Net Perls

Sort. In C# we sort collections of elements (like those stored in a List) with built-in methods. We can process arrays and Lists with value elements, and more complex types.

On an array of classes, sorting can be done based on keys (like a specific property of the object). And we can even sort 2 arrays at once—one array is the sort key array.

First example. This program creates a character array of 3 chars. It then calls Array.Sort on the char array reference—and the array elements are reordered.

Tip There is no need to assign to the result of Array.Sort. This would result in a compile-time error.

Detail The Array.Sort method is a generic method. Sometimes the C# compiler can derive the type—so we can omit it in our code.

Generic

Also We use the string constructor on our char array to print the strings to the console.

using System; char[] array = { 'z', 'a', 'b' }; // Convert array to a string and print it. Console.WriteLine("UNSORTED: " + new string(array)); // Sort the char array. Array.Sort<char>(array); Console.WriteLine("SORTED: " + new string(array));

UNSORTED: zab SORTED: abz

String arrays. Here we call the static Array.Sort method and use it to sort a string array in-place. The result is an alphabetical sort. With strings, all the characters are considered.

Step 1 We pass the string array reference to the Array.Sort static method. No value is returned by Array.Sort.

Array.Sort

Step 2 We use the foreach-loop to print out all the pet names. Strings can be sorted in the same way as chars—with Array.Sort.

using System; string[] pets = new string[] { "dog", "bird", "cat" }; // Step 1: invoke Array.Sort method on string array. Array.Sort(pets); // Step 2: loop over strings in array and print them. foreach (string pet in pets) { Console.WriteLine(pet); }

bird cat dog

Alphabetize chars. Occasionally, we need to alphabetize the letters in a string. We can convert a string to a character array, and then convert the sorted char array back to a string.

using System; using System.IO; string value = "bird"; // Get char array, then sort it, and convert back to string. var letters = value.ToCharArray(); Array.Sort(letters); string result = new string(letters); Console.WriteLine("ALPHABETIZE: {0} -> {1}", value, result);

ALPHABETIZE: bird -> bdir

Query. Next we take a string array and use a LINQ query expression to alphabetically order its contents. We order the strings—not the characters in them.

LINQ

Note We see that the orderby keyword results in the same output as the Array.Sort method.

However When we use a query, it returns an IEnumerable collection. This is a collection that we enumerate (loop over) with foreach.

IEnumerable

using System; using System.Linq; string[] roadNames = new string[] { "Mill St.", "Robin St.", "Echo Dr.", "Iron Dr." }; // Sort the roads. var result = from name in roadNames orderby name select name; // Evaluate our query. foreach (string value in result) { Console.WriteLine(value); }

Echo Dr. Iron Dr. Mill St. Robin St.

Reverse query. We sort strings from Z to A, not A to Z. This is called reverse alphabetic order. LINQ here is used with a query expression.

Tip Ascending means to go from lowest to highest (A to Z). This is the default ordering, so we do not need to specify it.

And A descending order means to go from highest to lowest (Z to A). We must explicitly specify this.

descending

Important The order by keyword is not a method. Instead it compiles into a method call. It is a query clause.

orderby

using System; using System.Linq; string[] trees = new string[] { "Elm", "Palm", "Redwood", "Oak" }; // Sort the trees from last to first. var result = from treeName in trees orderby treeName descending select treeName; // Write all tree names. foreach (string value in result) { Console.WriteLine(value); }

Redwood Palm Oak Elm

List. This is a generic collection, with internal array storage. List not an array type in the C# language. We therefore have to use its separate Sort method.

Sort List, Lambda

Also We can use LINQ with the same syntax on List as used on arrays. Both arrays and Lists implement the IEnumerable interface.

Important The fruit names are sorted alphabetically, not by how tasty the fruit is. This is why "apple" comes first.

using System; using System.Collections.Generic; List<string> fruitNames = new List<string>() { "mango", "pineapple", "kiwi", "apple", "tomato" }; // Sort the fruit in alphabetical order. fruitNames.Sort(); // Print the sorted fruit. foreach (string fruit in fruitNames) { Console.WriteLine(fruit); }

apple kiwi mango pineapple tomato

Copy, sort. Many sort methods operate in-place. This means the unsorted, original collection no longer exists. To retain the original order, we must first copy the elements.

Here The List elements are sorted, but the original array is left alone. This requires the .NET Framework version 4.0 or later to compile.

string.Join

using System; using System.Collections.Generic; string[] array = { "zebra", "parrot", "ant" }; // Copy the list, then sort it. List<string> copy = new List<string>(array); copy.Sort(); // Display the collections. Console.WriteLine(string.Join(",", array)); Console.WriteLine(string.Join(",", copy));

zebra,parrot,ant ant,parrot,zebra

Sort 2 things. Suppose we want to sort by one part of your data (an int) and then by another part (another int). This can be done with a comparison method, or with a LINQ expression.

Part 1 ComparisonTwoTuples calls CompareTo twice: it first compares Item1. If that is equal, it uses CompareTo on Item2.

Part 2 We use an orderby clause with a second part. Notice how we can specify ascending and descending.

Note The CompareTo method (used in ComparisonTwoTuples) returns 0 when two values compare to be equal.

Result We sort on the first item in the tuples—from low to high. And we sort on the second item, from high to low (descending).

using System; using System.Collections.Generic; using System.Linq; class Program { static List<Tuple<int, int>> GetData() { var data = new List<Tuple<int, int>>(); data.Add(new Tuple<int, int>(10, 5)); data.Add(new Tuple<int, int>(10, 4)); data.Add(new Tuple<int, int>(1, 6)); data.Add(new Tuple<int, int>(1, 100)); return data; } static int ComparisonTwoTuples(Tuple<int, int> a, Tuple<int, int> b) { // Here we sort two times at once, first one the first item, then on the second. // ... Compare the first items of each element. var part1 = a.Item1; var part2 = b.Item1; var compareResult = part1.CompareTo(part2); // If the first items are equal (have a CompareTo result of 0) then compare on the second item. if (compareResult == 0) { return b.Item2.CompareTo(a.Item2); } // Return the result of the first CompareTo. return compareResult; } static void Main() { // Use comparison. var data = GetData(); data.Sort(ComparisonTwoTuples); Console.WriteLine("::COMPARISON::"); foreach (var tuple in data) { Console.WriteLine(tuple); } // Use LINQ orderby. var data2 = GetData(); var sorted = from tuple in data2 orderby tuple.Item1 ascending, tuple.Item2 descending select tuple; Console.WriteLine("::ORDERBY::"); foreach (var tuple in sorted) { Console.WriteLine(tuple); } } }

::COMPARISON:: (1, 100) (1, 6) (10, 5) (10, 4) ::ORDERBY:: (1, 100) (1, 6) (10, 5) (10, 4)

Bool. A bool array is sorted from false to true. When sorting, false is considered as 0 and true is considered as 1. We can use ascending or descending sorts.

bool Sort

using System; var values = new bool[] { true, false, true }; // Sort bool array. Array.Sort(values); foreach (var value in values) { Console.WriteLine(value); }

False True True

Reverse. Reversing an array of elements simply changes the order from back to front. It does not alphabetize or reorder the elements in an ascending or descending order.

Array.Reverse

using System; var values = "abc".ToCharArray(); // Reverse the values. Array.Reverse(values); foreach (var value in values) { Console.WriteLine(value); }

c b a

Benchmark, quicksort. I tested the sort methods on both arrays and Lists. The performance of these methods was close. Lists and arrays are sorted in about the same amount of time.

Info In these modern times, optimized algorithms are built into frameworks. The methods on this page are implemented with quicksort.

Version 1 We sort an array of 1000 elements that are not in ascending order, but are not random. Modulo returns alternating elements.

Modulo

Version 2 We sort a List with the same elements as the array. Only the first sort moves the elements around.

Result The array and List are processed in about the same time, so the underlying algorithm is likely the same in each case.

using System; using System.Collections.Generic; using System.Diagnostics; const int _max = 100000; // Create array and list. var array = new int[1000]; for (int i = 0; i < array.Length; i++) { array[i] = i % 10; } var list = new List<int>(array); // Version 1: sort an array. var s1 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { Array.Sort(array); if (array[0] != 0) { return; } } s1.Stop(); // Version 2: sort a List. var s2 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { list.Sort(); if (list[0] != 0) { return; } } s2.Stop(); Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns")); Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns"));

11115.19 ns Array.Sort 11110.94 ns List.Sort

Benchmark, LINQ sort. There is a performance penalty to using query expressions and LINQ methods. These methods act on IEnumerable, and this adds indirection.

Version 1 This version of the code uses Array.Sort on a small array of ints to sort in ascending order.

Version 2 Here we use a query expression, and the FirstOrDefault() method, to perform the same tasks as version 1.

FirstOrDefault

Result There is significant overhead to using LINQ on small int arrays. For low-level things like int arrays, prefer Array.Sort.

using System; using System.Diagnostics; using System.Linq; const int _max = 1000000; // Version 1: create array and sort it with Array.Sort. var s1 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { var data = new int[] { 10, 20, 0, -10, 100, -100 }; Array.Sort(data); if (data[0] != -100) { return; } } s1.Stop(); // Version 2: create array, sort it with LINQ, and test first element. var s2 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { var data = new int[] { 10, 20, 0, -10, 100, -100 }; var result = from element in data orderby element select element; if (result.FirstOrDefault() != -100) { return; } } s2.Stop(); Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns")); Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns"));

52.66 ns Array.Sort 263.05 ns Query expression

Benchmark, SortedSet. Collections like SortedSet can keep elements sorted as we add them. These can lead to performance improvements if you need sorted elements.

SortedSet

Version 1 We create a SortedSet and add 4 strings to it. Then we access Min and Max to ensure the elements are sorted.

Version 2 We create a List and add 4 strings to it, and then call Sort() to order the elements.

Result Keeping the elements sorted as we add them is faster overall. Note that the SortedSet cannot accept duplicate elements.

using System; using System.Collections.Generic; using System.Diagnostics; const int _max = 1000000; // Version 1: use SortedSet to keep elements sorted. var s1 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { SortedSet<string> set = new SortedSet<string>(); set.Add("x"); set.Add("y"); set.Add("a"); set.Add("0"); var first = set.Min; var last = set.Max; if (first != "0" || last != "y") { return; } } s1.Stop(); // Version 2: use List and call Sort to sort elements. var s2 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { List<string> list = new List<string>(); list.Add("x"); list.Add("y"); list.Add("a"); list.Add("0"); list.Sort(); var first = list[0]; var last = list[list.Count - 1]; if (first != "0" || last != "y") { return; } } s2.Stop(); Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns")); Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns"));

617.35 ns SortedSet, 4 Add calls 747.52 ns List, 4 Add calls, Sort

Summary. Sorting uses method calls. With arrays and lists, it is important to copy a collection first if we want to keep the original. With query syntax we simplify sorting.