Learn/C#/12. Sorting and searching
Lesson 12 of 15
Sign in

C#, lesson 12

Sorting and searching

Sorted data is easier to read and much faster to search. .NET does the sorting for you; your job is to describe the order you want.

Sorting in natural order

Array.Sort and List<T>.Sort sort in place. They are fast, but not stable: items that compare as equal may end up in any order. If ties matter, say how to break them (see below).

A word about strings. By default .NET compares strings using the rules of the current culture (language settings), which can differ between computers. For predictable program output, pass StringComparer.Ordinal (compare character codes) or string.CompareOrdinal(a, b).

Custom order with a comparison

List<T>.Sort accepts a that compares two items and returns a negative number if the first should come first, a positive number if the second should, and zero for a tie. Every built-in type has a method that does exactly that, so you rarely compute the number yourself:

2 exercises to try what you just read.

Exercise 1

Leaderboard

Press Ctrl Enter or Check to test your code.

Exercise 2

Price finder

Press Ctrl Enter or Check to test your code.

lambda
CompareTo

Swapping a and b in b.Score.CompareTo(a.Score) is how you get descending order.

Sorting with LINQ

LINQ (the subject of lesson 14) offers a more readable, stable alternative that returns a new sequence instead of changing the original:

Read it as "by score, highest first, then by name".

Searching: linear versus binary

Checking every element until you find a match is a linear search; list.IndexOf(x) does that. On a million items it may take a million checks.

If the data is sorted, binary search is far faster. Compare the target with the middle element. If they match, you are done. If the target is smaller, it can only be in the left half; otherwise it is in the right half. Every step halves the range, so a million items need about 20 steps.

The built-in versions are Array.BinarySearch(array, value) and list.BinarySearch(value). When the value is missing they return a negative number: the bitwise complement (~) of the index where it would be inserted, so ~result tells you where it belongs. Binary search on unsorted data returns nonsense, so always sort first.

Further reading

  • Array.Sort
  • List<T>.Sort
  • Sorting data with LINQ
  • Array.BinarySearch

The first line is a number N, followed by N lines of name score. Print the leaderboard: the highest score first, and players with equal scores in ordinal (character code) order of their names. Each line is <rank>. <name> <score>, where rank is simply the position 1, 2, 3, …

Sample input:

Sample output:

The first line holds distinct whole-number prices in ascending order, separated by spaces. Each following line is a price to look up. Write your own static int BinarySearch(int[] a, int target) (do not use Array.BinarySearch) and, for each query, print Found at <index> (index counted from 0) or Not found.

Sample input:

Sample output:

int[] scores = [42, 7, 19];
Array.Sort(scores);                    // [7, 19, 42]

List<string> names = ["mia", "Leo", "ana"];
names.Sort(StringComparer.Ordinal);    // [Leo, ana, mia]  (by character code)
names.Sort(StringComparer.OrdinalIgnoreCase); // [ana, Leo, mia]
List<Player> players = [new("Zoe", 30), new("Al", 50), new("Bea", 30)];

players.Sort((a, b) =>
{
    int byScore = b.Score.CompareTo(a.Score);               // high scores first
    return byScore != 0 ? byScore : string.CompareOrdinal(a.Name, b.Name);
});
// Al 50, Bea 30, Zoe 30

record Player(string Name, int Score);
using System.Linq;

var ranked = players
    .OrderByDescending(p => p.Score)
    .ThenBy(p => p.Name, StringComparer.Ordinal)
    .ToList();
static int BinarySearch(int[] a, int target)
{
    int low = 0, high = a.Length - 1;
    while (low <= high)
    {
        int mid = low + (high - low) / 2;   // avoids overflow on huge arrays
        if (a[mid] == target) return mid;
        if (a[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;   // not found
}
4
zoe 30
al 50
bea 30
cy 10
1. al 50
2. bea 30
3. zoe 30
4. cy 10
3 8 15 23 42 99
23
4
3
Found at 3
Not found
Found at 0