A. Programming Concepts and Skills · Data Types, Files and Expressions

Non-Numeric Comparisons: Comparing and Sorting Strings

A1.3 A1.2About 70 minutes

Learning goals

I can predict the result of <, >, == and != on strings using code points and lexicographic order.
I can write a comparison function that returns a negative, zero or positive result, like Java's compareTo.
I can sort strings case-insensitively and accent-insensitively with a key function.
I can explain the difference between == and is, and between Python and Java string equality.

Words to know

lexicographic order
Dictionary-style order: compare character by character; the first difference decides; a prefix comes before the longer string.

code point
The number Unicode gives a character. String comparison in Python compares code points.

case-insensitive comparison
Comparing text while ignoring capital versus small letters, e.g. using casefold() on both sides.

key function
A function passed as key= to sorted, min, max or list.sort; items are compared by the key's result instead of by themselves.

Unicode normalization
Converting text to a standard form (NFC or NFD) so that the same visible characters are stored the same way.

identity
Whether two names refer to the very same object (is), as opposed to equal contents (==).

three-way comparison
A comparison that returns negative, zero or positive for less, equal or greater, such as Java's compareTo.

Is "Zebra" less than "apple"?

Comparing numbers is easy. But programs compare text all the time: sorting a class list, finding a name in a phone book, checking a password, ordering songs by title. What does it mean for one string to be "less than" another?

In this lesson you will learn the exact rule computers use, why that rule surprises people ("Zebra" < "apple" is True!), and how to compare text the way a human reader expects, including names with accents such as Montréal and Lévis.

The rule: lexicographic order by code point

Python compares two strings like this:

Look at the first character of each. If they differ, the string whose character has the smaller code point is smaller. Done.
If they are equal, move to the next character and repeat.
If one string runs out first (it is a prefix of the other), the shorter string is smaller.
If both run out together, the strings are equal.

The rest of the strings after the first difference is never examined.

Lexicographic comparison works like a dictionary: compare the strings character by character using their code points. The first difference decides ("e" is 101, "i" is 105). Matching letters (green) are skipped.

print("sled" < "slide", "snow" < "snowy", "" < "a")

print("Zebra" < "apple", "10" < "9", "maple" == "Maple")

print(min(["oak", "Elm", "birch"]), max("Kingston"))

Comparison operators work on strings. A prefix is smaller than the longer string. Capital letters come before all small letters, and digits are compared as characters, so "10" < "9". Output, line by line: True True True | True True False | Elm t

Where characters sit in Unicode (not to scale). Space comes before digits, digits before capitals, capitals before small letters, and accented letters such as É (201) and é (233) after all of them. That is why "Zebra" < "apple" and "Montréal" can sort strangely.

Three-way comparison

Many languages and libraries describe order with one number instead of a True/False answer:

negative: a comes before b,
zero: they are equal,
positive: a comes after b.

Java's a.compareTo(b) works this way, and so does C's strcmp. It is handy because one call answers all three questions. Here is the algorithm written out in Python:

def compare(a, b):

"""Return -1 if a < b, 0 if a == b, 1 if a > b, comparing code points

(the same rule as Python's < and Java's compareTo sign)."""

for x, y in zip(a, b): # pairs of characters

if x != y:

return -1 if ord(x) < ord(y) else 1

# no difference in the shared part: the shorter string is smaller

if len(a) == len(b):

return 0

return -1 if len(a) < len(b) else 1

print(compare("sled", "slide"), compare("snowy", "snow"), compare("ice", "ice"))

Lexicographic comparison written by hand. It returns a negative, zero or positive result, which is exactly how Java's compareTo and C's strcmp report order. Output: -1 1 0

Worked example

Example 1: Predict the order

Sort by hand, as Python's plain sorted would: ["apple", "Apple", "apple pie", "100", "20", "_x"]. (The code of "_" is 95.)

Compare first characters by code point: "1" (49), "2" (50), "A" (65), "_" (95), "a" (97).
So the order starts "100", "20" (digits compared as characters: 1 before 2, even though 100 > 20 as numbers), then "Apple", then "_x".
"apple" and "apple pie" share the first 5 characters. "apple" has run out, so it is a prefix and comes first.
Check in Python: sorted([...]).

['100', '20', 'Apple', '_x', 'apple', 'apple pie']

Comparing the way people expect

The code-point rule is fast and consistent, but it does not match a dictionary or a phone book:

Case: all capitals come before all small letters. Fix: compare casefold() copies. (casefold is like lower but also handles letters such as the German ß, which becomes ss.)
Accents: é (233) comes after z (122). Fix: remove accent marks with unicodedata, as shown below.
Numbers inside text: "file10" sorts before "file9". Fix: a key that turns digit runs into ints (see Challenge).

You do not change the data. You pass a key function to sorted, min, max or list.sort. Python calls the key on each item and compares the results.

cities = ["Ottawa", "Montréal", "Lévis", "London", "lethbridge", "Iqaluit"]

print(sorted(cities))

print(sorted(cities, key=str.casefold))

print("Straße".lower(), "Straße".casefold())

Plain sorted puts "lethbridge" last because small letters come after all capitals. A key function compares a changed copy of each string; str.casefold is a stronger version of lower meant for case-insensitive matching. Output, line by line: ['Iqaluit', 'London', 'Lévis', 'Montréal', 'Ottawa', 'lethbridge'] | ['Iqaluit', 'lethbridge', 'London', 'Lévis', 'Montréal', 'Ottawa'] | straße strasse

import unicodedata

def plain(text):

"""Return text in a form for comparing: accents removed, case folded."""

decomposed = unicodedata.normalize("NFD", text) # é -> e + accent mark

no_marks = "".join(ch for ch in decomposed if not unicodedata.combining(ch))

return no_marks.casefold()

places = ["Îles-de-la-Madeleine", "Iqaluit", "Lévis", "London", "lethbridge"]

print(sorted(places))

print(sorted(places, key=plain))

print("é" == "e\u0301", unicodedata.normalize("NFC", "e\u0301") == "é")

Sorting the way a reader expects. The last line shows that one visible é can be stored two ways (one code point, or e plus a combining accent). They are only == after normalizing both. Output, line by line: ['Iqaluit', 'London', 'Lévis', 'lethbridge', 'Îles-de-la-Madeleine'] | ['Îles-de-la-Madeleine', 'Iqaluit', 'lethbridge', 'Lévis', 'London'] | False True

Real-world sorting

Proper sorting for a particular language (French puts accented letters in a particular place, for example) is called collation. Python's locale module and libraries such as ICU do it properly. For school projects, casefold plus accent removal is a sensible approximation, and you should say so in a comment.

Worked example

Example 2: Equality versus identity

A student writes if answer is "yes": and it sometimes fails even when the user typed yes. Explain and fix.

== asks: do these two strings contain the same characters? is asks: are these the same object in memory?
A string built at run time (from input(), a file, or slicing) is usually a new object, so is can be False even when the text matches. Whether Python reuses objects is an implementation detail you must not rely on.
Fix: if answer == "yes":. Even better, ignore case and extra spaces: if answer.strip().casefold() == "yes":.
Java has the same trap the other way around: == on two String objects compares references, and you must write a.equals(b) (or a.equalsIgnoreCase(b)) to compare text.

Use == (or .equals in Java) to compare string contents; use is only for None checks such as if x is None:.

Just for fun

Why did the sorting program put "Zebra" before "aardvark"?

Because in Unicode, a capital Z (90) shouts louder than a small a (97). Capitals always cut the line.

Hands-on activity

Phone book versus Python

You need: Python and a list of 12 names from your contacts, a team roster, or a list of Canadian towns (include at least two with accents, two starting with small letters, and two with numbers, such as "Highway 7" and "Highway 11").

Sort the list by hand the way a printed phone book would.
Sort it with plain sorted() and write down every place where Python disagrees with you. Explain each one using code points.
Write a key function that fixes case and accents, and sort again.
Bonus: make "Highway 7" come before "Highway 11".

What to look for: each disagreement explained by a code point (capitals before small letters, é after z, "1" before "7"), and a final key that matches your hand-sorted list.

Your turn

True or False? (a) "cat" < "catalogue" (b) "Cat" < "cat" (c) "9" > "10" (d) "b" > "apple"

What does compare("maple", "map") return, using the function in this lesson?

What does max(["pine", "Spruce", "cedar"]) return?

Write the call that finds the alphabetically first name in a list names, ignoring case.

Why is "Élise" > "Zoé" True in Python?

A user types Yes (with spaces). Write a condition that accepts it as yes.

What is the Java equivalent of Python's a == b for two String objects, and why not ==?

More practice: warm-up

Is "apple" < "banana"?

Is "Apple" == "apple"?

Which is smaller, "car" or "cart"?

What does "Hi".casefold() give?

What does sorted(["b", "a", "C"]) give?

More practice: on your own

Sort by Python's plain rules: ["hockey", "Hockey", "hockey stick", " hockey", "H0ckey"].

Trace compare("sled", "slide"): which pair of characters decides, and what is returned?

Write a one-line sort that orders a list of words by length, and words of equal length alphabetically ignoring case.

Two strings print exactly the same on screen but == says False. Give two possible reasons and how to check.

Why is it a mistake to check a password with a case-insensitive comparison?

Challenge

Write a key function natural_key(s) so that "file9" sorts before "file10". Hint: re.split(r"(\d+)", s) splits text into non-digit and digit pieces.

Prove that the three-way compare function is consistent: if compare(a, b) is −1 then compare(b, a) is 1.

Lexicographic comparison of two strings of length n can take up to n character comparisons. Give an example pair that needs all n, and one that needs only 1.

Check your understanding

Quiz

Which comparison is True in Python?

Which list is sorted by plain sorted()?

What does Java's "cab".compareTo("cat") return the sign of?

Which call sorts names ignoring capital letters?

Why should you not write if word is "done":?

Two strings both display as "café" but are not equal. What is the most likely cause?

For parents and teachers

Big idea: A1.3 asks students to use non-numeric comparisons, such as strings and the "comparable interface" (objects that know how to compare themselves, taught in the lesson Making Objects Comparable). Here students learn the exact rule for string order and how to customize it. It also touches A1.2, since every comparison is really between character codes.

How to help: the phone-book activity works well together: you sort by hand, your teen predicts where Python will disagree.

Common difficulties:

Thinking string comparison is by length. It is character by character.
Expecting "10" < "9" to be False.
Using is instead of ==.
Forgetting that sorted returns a new list, while list.sort() changes the list and returns None.