Monday, 19 October 2020

C# - Lexicographic Order

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 numberslexicographic 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