CS1102C Miniature 10

How are C or C++ strings sorted?

C and C++ strings are sorted by an ordering known as lexicographical ordering. Lexicographical ordering seems to be a big name, but it is nothing more than how words are sorted in a dictionary. Note that lexicographical ordering is applied when the C strcmp() function is used or when comparison of C++ strings is done using any of the <, >, <= and >= operators.

Here are the rules for applying lexicographical ordering on two different strings s1 and s2:

If s1 is a prefix of s2, then s1 comes before s2. Similarly, if s2 is a prefix of s1, then s2 comes before s1.
Otherwise, let k be the least index such that s1[k] is not the same as s2[k]. Then the ordering of s1 and s2 is the same as the ordering of the characters s1[k] and s2[k].

In the American Standard Code for Information Interchange (ASCII) character set which all of us are using, the space character comes before the numeric characters, and the numeric characters comes before the alphabetical characters.

The lexicographical ordering is suitable for sorting words, but is not suitable for sorting numerical strings. A quirk in lexicographical ordering is that "week1" comes before "week10", which comes before "week2".

It is interesting to note that Microsoft has applied exact lexicographical ordering for their Windows Explorer (called File Manager in Windows 3.1 and earlier) until a couple of years ago, when they used a smarter algorithm. In Windows XP and Windows ME, we can see that "file100" comes after "file99". Apparently some of the Linux operating systems have yet to use the smarter algorithm.

An exercise: how do you modify the lexicographical ordering algorithm to take care of numbers in the strings?

Back to Index