C#, lesson 12
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.
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).
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.
CompareToSwapping a and b in b.Score.CompareTo(a.Score) is how you get descending order.
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".
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.
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 101. al 50
2. bea 30
3. zoe 30
4. cy 103 8 15 23 42 99
23
4
3Found at 3
Not found
Found at 0