What is Lexicographical Order?
Lexicographical Order is a way of arranging words or
sequences in the same order as they would appear in a dictionary. In this
ordering, the sequences are compared character by character, based on their alphabetical
order (or numerical order for digits).
Key Points:
- The
comparison starts with the first character of each sequence.
- If
the first characters are the same, the comparison moves to the next
character.
- Shorter
sequences come before longer ones if one is a prefix of the other.
Example 1: Words
Consider the words:
apple, banana, bat, batman.
- Compare
the first letters: a comes before b, so apple comes first.
- Compare
banana and bat:
- The
first letters are the same (b), so compare the second letters (a).
- Since
a in banana comes before a in bat, compare the third letters.
- n
in banana comes before t in bat. So, banana comes before bat.
- bat
and batman:
- bat
is a prefix of batman, so bat comes first.
Final order:
apple, banana, bat, batman.
Example 2: Numbers as Strings
Consider the numbers as strings:
101, 11, 110, 2.
- 101
vs 11:
- Compare
the first digits: 1 is equal.
- Compare
the second digits: 0 in 101 comes before 1 in 11. So, 101 comes first.
- 11
vs 110:
- 11
is a prefix of 110, so 11 comes first.
- 110
vs 2:
- Compare
the first digits: 1 in 110 comes before 2. So, 110 comes first.
Final order:
101, 11, 110, 2.
Application:
Lexicographical order is used in:
- Sorting
algorithms.
- String
manipulations.
- Searching
in dictionaries and databases.
