Basics of Lexicographic, Dictionary, and Alphabetic Ordering

Is lexicogrpahic ordering the same as the order in a dictionary?

Yes, lexicographic ordering is the same as the order in which words appear in a dictionary. It’s a way of arranging words based on the alphabetical order of their component letters. This is the method often used to sort strings of text in a way that is easy to understand and locate.

Do lexicographic, dictionary and alphabetic ordering all mean the same thing?

Not exactly, but they are closely related.

  1. Lexicographic ordering: This is a mathematical term usually used for sorting arrays of more complex structures based on some sort of priority of their elements. In lexicographic ordering, elements are compared one by one, from the first element to the last, until a difference is found. It is not limited to alphabetical characters and can involve numbers or other types of data as well.

  2. Dictionary ordering: This term usually refers specifically to the way words are sorted in a dictionary, which is a type of lexicographic ordering but can involve additional rules. For example, hyphenated words, acronyms, or names may be sorted differently than they would be in a simple lexicographic sort.

  3. Alphabetic ordering: This is the simplest form of ordering and typically refers to sorting letters purely based on their position in the alphabet, without considering any additional complexities like strings of multiple words, special characters, etc.

While these terms are often used interchangeably in casual conversation, they can mean different things in specific contexts.

1. Lexicographic Ordering

In computer science, this ordering is often used to sort arrays or lists of tuples or strings. Consider two lists of tuples:

  • List A: [(1, 2), (1, 3), (1, 1)]
  • List B: [(1, “apple”), (2, “banana”), (0, “cherry”)]

Sorting them lexicographically, we get:

  • Sorted A: [(1, 1), (1, 2), (1, 3)]
  • Sorted B: [(0, “cherry”), (1, “apple”), (2, “banana”)]

Here, elements are compared one by one: first elements are compared first, and if they are equal, the second elements are compared, and so on.

2. Dictionary Ordering

Imagine three words:

  • Apple
  • App-le (hypothetical hyphenated word)
  • app (all lowercase)

In a typical English dictionary:

  • Apple comes before app, as dictionaries often treat all characters as case-insensitive for the purpose of ordering.
  • “App-le” would often come near “Apple” but not necessarily directly adjacent, depending on the dictionary’s rules for hyphens.

3. Alphabetic Ordering

Consider the following characters:

  • A, B, C, a, b, c

In strict alphabetic ordering, they might be sorted considering ASCII values:

  • A (65), B (66), C (67), a (97), b (98), c (99)

Or, they could be sorted case-insensitively:

  • A, a, B, b, C, c

In alphabetic ordering, we only care about the alphabet rank of individual characters, not the whole string or additional characters like hyphens or spaces.

Key Takeaways:

  • Lexicographic ordering considers the sequence of elements and may include different types of data.
  • Dictionary ordering focuses on words, typically ignores case, and might have special rules for special characters.
  • Alphabetic ordering is the simplest, often considering just the alphabet rank, and could be case-sensitive or case-insensitive depending on the context.