Lexicographical Order in Java

Introduction

Lexicographical or lexical order is a common name used for the alphabetic order or the sequence of ordered symbols in the dictionaries or elements of an ordered set. It gets its name from the word 'lexicon,' which symbolizes the conventional ordering of the alphabets used to build words. It is a notion that can only be used in dictionaries. But this is not true, as it is also commonly used for dates and numbers. The same holds for programming. The lexicographical or dictionary order sorts elements of the array by comparing each pair in the formal order of alphabets, dates, or numbers.

Understanding the Formal Notion of Lexicographical Order

Let's understand the formal notion of lexicographical order, knowing what it is really about.

• It starts with a finite and ordered set $A$, often called the alphabet. For any two elements $a$ and $b$ in set A that are not the same, either $a<b$ or $b<a$.
• The words of $A$ are sequences of fixed length, including empty sequences of zero length or no symbol.
• The ordering of these finite words is done as follows:
  • If there are two different words of the same length named $a$ and $b$, the order of the two depends on the alphabetic order of the symbols. If $i$ is the first place where the two words differ, then $a<b$ if and only if $ai < bi$ in the order of the elements of set $A$.
  • If the two words are of different lengths, they are thought to be filled with blanks smaller than every element of $A$ at the end until they are of the same length. After that, they are compared using the previous point.

Implementing Lexicographical Order in Java

We can implement lexicographical order in Java by comparing and sorting elements according to a finite ordered set. Arranging the words in lexicographical order means reordering them according to their alphabetical components. It can be done alphabetically or lexically. We can implement this by applying any sorting technique or the sort() function. Let's dive deeper into it and implement them one by one.

Using Any Sorting Technique to Sort array Elements.

The following technique uses the compareTo method of the String class. The compareTo method compares the current string with the given string in the lexicographical order by returning positive, negative, or zero numbers.

Function

The following function compares the String1 to the String2 provided as the parameter.

Example

Let's understand it with an example.

Running the above code gives the following output:

Output:

In the above example, we have created a class JavaExample that calls the main method. The main method initializes the input string array and calls two functions passing the string array as parameters. The function printArray prints the element of the array, and the function sortLexicographically helps us sort the string array in Lexicographic or Dictionary order.

Here, we are sorting elements in lexicographical order using any sorting method used to sort array elements. Two strings are compared using the compareTo() method of the String class.

• It returns zero if both the strings are lexicographically equal.
• It returns a number less than zero if the given string is lexicographically greater than the current string.
• It returns a number greater than zero if the argument is lexicographically lesser than the current string.

The ith element is compared to all the elements coming after it in the list. We can analyze that after implementing the sorting method, the string array elements are sorted according to the alphabetical order from names starting from A and ending at Z.

The time complexity of the above code is $O(n^2)$ (for sorting; compareTo method used inside has its implementation for comparing strings). Here, n is the size of the array.

Using sort() Function Present in Arrays class in util Package in Java

The following approach uses the sort() function present in Arrays class in util package in java.

Function

In the given function, the first parameter takes the name of the array of strings to compare. The second parameter ensures that the case of the string is ignored.

Example

The following code helps us sort the elements in Lexicographical Order using the sort() method, which is present in the Arrays class in the util package in Java.

Output:

In the above example, the sort method takes two arguments. The first is the array's name, and the second specifies the method to ignore the case while sorting. The above code's time complexity is O(n log n).

Example: Comparing Two strings by Lexicographical Order in Java

There are two methods to compare strings in Java:

• Using the user-defined function
• Using the previously defined compareTo() method.

Let's explore them one by one using examples.

compareTo() Method

The following code is an example of how the compareTo() method works to compare two strings in the lexicographical order.

Example 1

Output:

Example 2

Output:

Example 3

Output:

In the above examples, we can see how the compareTo function works. A class named JavaExample is created where the main method() is implemented. Two strings are initialized and compared with each other. Both can be the same or different, as discussed in the previous examples. The compareTo function compares the strings str1 and str2 and returns positive, negative, or zero depending on the string. If the returned value is less than 0, str1 is greater than str2. If the returned value exceeds 0, str1 is less than str2. The function returns zero when both the strings are equal.

By User-Defined Function

Apart from using the predefined compareTo() function for comparing strings and sorting in lexicographical order, we can also create user-defined functions the same.

Let's see it with an example.

Output:

In the above examples, we can see how a user-defined comparator function works. A class named JavaExample gets created to implement the main method(). We initialize five strings that get compared using the user-defined function compareString. The variable lim stores the minimum length of the two strings. A variable k is defined to traverse the strings until they encounter the first non-matching character. The function returns the difference of the ASCII values of the non-matching character. If it encounters two strings like "Pen" and "Pentab", then the difference in the length is returned. You can understand it more clearly using the examples.