Lexicographic Order
To put items in order, there
must be a way to compare two items. With strings, the usual order is Lexicographic
Order. This is dictionary order, except that all the uppercase letters preceed all the lowercase
letters. This order is what the compareTo()
method of class String
uses.
Two
strings are lexicographically equal if they are the same length and contain the
same characters in the same positions. In this case, stringA.compareTo(
stringB )
returns 0.
Otherwise, stringA.compareTo(
stringB )
returns a negative value
if StringA
comes first
and a positive value if StringB
comes first.
Memory
Aid: think of the strings in a dictionary as arranged from smallest to largest.
Then stringA - stringB
would
produce a negative values if stringA
came before StringB
.
To
determine which string comes first, compare corresponding characters of the two
strings from left to right. The first character where the two strings differ
determines which string comes first. Characters are compared using the Unicode
character set. All uppercase letters come before lower case letters. If two
letters are the same case, then alphabetic order is used to compare them.
If
two strings contain the same characters in the same positions, then the
shortest string comes first.
|
Relation |
|
stringA.compareTo(
stringB ) |
stringA |
Less Than |
stringB |
Negative Integer |
stringA |
Equal |
stringB |
Zero |
stringA |
Greater Than |
stringB |
Positive Integer |
Expression |
Evaluates
to |
Explanation |
"Zebra".compareTo("ant") |
Negative Integer |
upper case 'Z' comes before lower case 'a' |
"Apple".compareTo("apple") |
Negative Integer |
upper case 'A' comes before lower case 'a' |
"apple".compareTo("orange") |
Negative Integer |
'a' comes before 'o' |
"maple".compareTo("morning") |
Negative Integer |
'a' comes before 'o' |
"apple".compareTo("apple") |
Zero |
same length, same characters in same positions |
"orange".compareTo("apple") |
Positive Integer |
'o' comes after 'a' |
"applecart".compareTo("apple") |
Positive Integer |
longer string "applecart" comes after
"apple" |
"albatross".compareTo("albany") |
Positive Integer |
't' comes after 'n' |
This is slightly confusing. Notice that stringA.compareTo(stringB)
returns
a negative integer when stringA
and stringB
are
in the correct order.
Learning
When applied to numbers, lexicographic order is increasing
numerical order, i.e. increasing
numerical order (numbers read left to
right). For example, the permutations of {1,2,3} in lexicographic order are 123, 132,
213, 231, 312, and 321. When applied to subsets, two subsets are ordered by
their smallest elements.
Lexicographical order is alphabetical order. The other type is numerical ordering. Consider the following values:
1, 10, 2
Those values are in lexicographical order. 10 comes after 2
in numerical order, but 10 comes before 2 in "alphabetical" order.
No comments:
Post a Comment