Lexicographical order in C
Lexicographical order is a way to arrange words or strings in a specific order based on the sequence of characters they contain. In this order, words or strings are sorted by comparing their characters from left to right. The comparison is done by considering the alphabetical position of each character in a given character set.
We start by comparing the first character of each word or string to determine the lexicographical order. If there is a difference, the word or string with the smaller character comes first. If the first characters are the same, we move on to the second characters and continue comparing until we find a difference or reach the end of one of the words or strings.
The process of comparing characters continues until the words or strings are fully evaluated. The resulting order places words or strings with "smaller" characters earlier and those with "larger" characters later.
Example 1:
Let's consider the words "TutorialsAndExamples" and "JavaTPoint". In lexicographical order, "JavaTPoint" comes before "TutorialsAndExamples" because the character 'J' comes before 'T' in the alphabet. The rest of the characters are not relevant for comparison since 'J' already establishes the order.
Example 2:
Let's consider the words "tabde" and "tabfg".
In lexicographical order, we compare the characters of the words from left to right. The first character of both words is 't'. Since they are the same, we move to the next character.
The second character of both words is 'a'. Again, they are the same, so we continue to the next character. The third character of both words is 'b'. Again, they are the same, so we move to the next character. The fourth character of both words is 'd' and 'f', respectively. Since 'd' comes before 'f' in the alphabet, "tabde" comes before "tabfg" in lexicographical order.
Method 1: for making a string lexicographical
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
void method1(char * origianl_string){
// In this method, we make a swap by comparing the characters
// it takes O(n^2) runtime
int string_length=strlen(origianl_string);
char temp;
for(int i=0; i<string_length-1; i++){
for(int j=0; j<string_length-i-1; j++){
if(origianl_string[j]>origianl_string[j+1]){
temp= origianl_string[j];
origianl_string[j]=origianl_string[j+1];
origianl_string[j+1]=temp;
}
}
}
}
int main(){
char original_string[100];
printf("Enter the original string \n");
scanf("%s",&original_string);
method1(original_string);
printf("%s",original_string);
return 0;
}
Output:
![Lexicographical order in C](https://static.tutorialandexample.com/c/lexicographical-order-in-c1.png)
Explanation:
- In this example, the method1 function takes a pointer to the original string as input and performs the sorting using the bubble sort algorithm. It swaps the characters if they are out of order, making multiple passes until the string is sorted in lexicographical order.
- original_string is an array of characters that holds the original input string.
- string_length is an integer variable that stores the length of the original string using the strlen() function from the <string.h> library.
- temp is a temporary variable used for swapping characters during the sorting process.
- In the method1 function, there are two nested for loops. The outer loop iterates from 0 to string_length-1, and the inner loop iterates from 0 to string_length-i-1. It ensures that the largest character is moved to the end of the string in each pass.
- Inside the inner loop, it compares adjacent characters using the condition if (original_string[j] >original_string[j + 1]). If the condition is true, it swaps the characters using the temporary variable temp.
- In the main() function, the user is prompted to enter the original string using printf() and scanf().
- After that, the method1 function is called and passes the original string as an argument for sorting it into lexicographical order.
- Finally, the sorted string is printed using printf().
Method 2: for making a string lexicographical
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
int compare_characters(const void* x, const void* y) {
return (*(char*)x - *(char*)y);
}
void method2(char* original_string) {
int string_length = strlen(original_string);
// using inbuilt function names qsort()
// for using qsort, we will use the stdlib standard library in c
qsort(original_string, string_length, sizeof(char), compare_characters);
}
int main(){
char original_string[100];
printf("Enter the original string \n");
scanf("%s",&original_string);
method2(original_string);
printf("%s",original_string);
return 0;
}
Output:
![Lexicographical order in C](https://static.tutorialandexample.com/c/lexicographical-order-in-c2.png)
Explanation:
- In this example, the compare_characters() function is defined, which is used by the qsort() function to compare characters. It takes two const void* arguments, representing the addresses of the characters being compared. Inside the function, the characters are cast to char* and their difference is returned.
- The method2() function is defined, which takes a pointer to the original string as input. It uses the qsort() function to sort the characters of the string in lexicographic order. The string length is calculated using strlen() to determine the number of elements to sort.
- In the main() function, the original_string array is declared to store the user input string.
- A prompt is displayed to the user to enter the original string using printf().
- The user input string is read using scanf().
- After that, the method2() function is called and passes the original_string as an argument to sort it in lexicographic order.
- Finally, the sorted string is printed using printf().
Method 3: for making a string lexicographical
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
void method3(char* original_string) {
int count[256] = {0};
// Assuming ASCII characters, each index represents each character
int string_length = strlen(original_string);
int i;
// Counting the frequency of each character
for (i = 0; i<string_length; i++)
count[original_string[i]]++;
int index = 0;
// Reconstructing the sorted string
for (i = 0; i< 256; i++) {
while (count[i] > 0) {
original_string[index] = i;
count[i]--;
index++;
}
}
}
int main(){
char original_string[100];
printf("Enter the original string \n");
scanf("%s",&original_string);
method3(original_string);
printf("%s",original_string);
return 0;
}
Output:
![Lexicographical order in C](https://static.tutorialandexample.com/c/lexicographical-order-in-c3.png)
Explanation:
- In this example, the method3 function takes a pointer to the original string as input (char* original_string).
- We initialize an array called count of size 256 to keep track of the frequency of each character. The assumption is that the string contains ASCII characters, so each index of the array represents a specific character.
- We use the strlen() function to get the length of the original string and store it in string_length.
- We iterate each character of the original string and increment the count of that character in the count array.
- After that, initialize an index variable to keep track of the position while reconstructing the sorted string.
- We use nested loops to reconstruct the sorted string:
- The outer loop iterates over each index from 0 to 255 (representing ASCII characters).
- The inner loop executes as long as the count of the current character is greater than 0.
- Inside the inner loop, we assign the character represented by the current index to the original_string array at the index position.
- Decreases the count of that character in the count array and increments the index.
- Once the loops finish, the original_string array contains the lexicographically sorted string.
- In the main() function, we declare the original_string array to store the input string provided by the user.
- After that, we use printf() to enter the original string and scanf() to reads the string.
- Calls the method3 function, passing the original_string array as an argument.
- Prints the sorted string using printf().