171

What is the exact meaning of lexicographical order? How it is different from alphabetical order?

7 Answers 7

191

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.

8
  • So in Lexicographical order, only the first digit will be considered of the value? Am I understanding right?
    – NDesai
    Sep 1, 2017 at 18:30
  • 35
    @NDesai No. If the first digits match, then the second digits will be compared; but it compares like a String - that is 10 comes before 2 but 111 comes after 10 (but also after 1000). Because 0 is less than 1. A lexical sort compares the characters in each string as characters, not integral values. Sep 1, 2017 at 22:57
  • 1
    @greybeard Wouldn't you want that in covalence order (it's been a while since a I had chemistry)? Mar 12, 2019 at 22:28
  • 6
    "lexicographical order is alphabetical order". This isn't quite true. Ordering of tuples has been described as lexicographic even where no alphabet is involved, e.g., (0,4,2) is less than (1,3,2) according to a lexicographic comparison. See here for example: en.wikipedia.org/wiki/Ordered_vector_space#Examples
    – jjramsey
    Mar 13, 2020 at 19:51
  • 2
    The common alphabetical order is an example of a lexicographical order.
    – Galen
    Jul 16, 2021 at 21:54
44

Alphabetical order is a specific kind of lexicographical ordering. The term lexicographical often refers to the mathematical rules or sorting. These include, for example, proving logically that sorting is possible. Read more about lexicographical order on wikipedia

Alphabetical ordering includes variants that differ in how to handle spaces, uppercase characters, numerals, and punctuation. Purists believe that allowing characters other than a-z makes the sort not "alphabetic" and therefore it must fall in to the larger class of "lexicographic". Again, wikipedia has additional details.

In computer programming, a related question is dictionary order or ascii code order. In dictionary order, the uppercase "A" sorts adjacent to lowercase "a". However, in many computer languages, the default string compare will use ascii codes. With ascii, all uppercase letters come before any lowercase letters, which means that that "Z" will sort before "a". This is sometimes called ASCIIbetical order.

0
30

This simply means "dictionary order", i.e., the way in which words are ordered in a dictionary. If you were to determine which one of the two words would come before the other in a dictionary, you would compare the words letter by the letter starting from the first position. For example, the word "children" will appear before (and can be considered smaller) than the word "chill" because the first four letters of the two words are the same but the letter at the fifth position in "children" (i.e. d ) comes before (or is smaller than) the letter at the fifth position in "chill" (i.e. l ). Observe that lengthwise, the word "children" is bigger than "chill" but length is not the criteria here. For the same reason, an array containing 12345 will appear before an array containing 1235. (Deshmukh, OCP Java SE 11 Programmer I 1Z0815 Study guide 2019)

1
  • 1
    "This"? your first sentence is ambiguous when reading the full question. Mar 3, 2022 at 17:14
10

Lexicographical ordering means dictionary order. For ex: In dictionary 'ado' comes after 'adieu' because 'o' comes after 'i' in English alphabetic system. This ordering is not based on length of the string, but on the occurrence of the smallest letter first.

5

I want to add an answer that is more related to the programming side of the term rather than the mathematical side of it.

Lexicographical order is not always an equivalent of "dictionary order", at least this definition is not complete in the realm of programming, rather, it refers to "an ordering based on multiple criteria".

For example, almost in all famous programming languages, there are standard tools for sorting collections of objects, now what if you want to sort a collection based on more than one thing? For instance, let's say you want to sort some items based on their prices first AND then based on their popularity. This is an example of Lexicographical Order.

For example in Java (8+), you could do something like this:

// sorts items from the cheapest AND the most popular ones
// towards the most expensive AND the least popular ones.
Collections.sort(items,
    Comparator.comparing(Item::price)
   .thenComparing(Item::popularity)
   .reversed()
);

And the Java documentation uses this term too, to refer to such type of ordering when explaining the "thenComapring()" method:

Returns a lexicographic-order comparator with another comparator.

1

Lexicographical order is nothing but the dictionary order or preferably the order in which words appear in the dictonary. For example, let's take three strings, "short", "shorthand" and "small". In the dictionary, "short" comes before "shorthand" and "shorthand" comes before "small". This is lexicographical order.

1
  • 11
    How is this different from the other answers that have been here for years? Perhaps you can find some unanswered questions that need an answer.
    – BoP
    Dec 22, 2021 at 23:09
0

Something that can help understand better the lexicographical ordering with string is the following example.

Given the following Python script:

words = ['apple', 'Banana', 'Cherry', 'Date', 'applepie']
max_word = max(words)
print(max_word)

The result will be surprisingly: 'applepie'

The motivation is that in the UNICAR sequence, the UPPERCASE LETTERs come before the LOWER CASE LETTERs.

To be more precise the UPPERCASE letters have a UNICHAR from 65 to 90 (A-Z) and the LOWERCASE letters have a UNICHAR from 97 to 122 (a-z).
So by sorting the above list because 'applepie' have the longest string with greater UNICHAR characters, it has been returned by the max built-in function.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.