What is a lexicographic order?

Overview

A lexicographic order is an arrangement of characters, words, or numbers in alphabetical order, that is, the letters are sorted from A-Z.

This is also known as dictionary order because it is similar to searching for a particular word in an actual dictionary. We start by searching for the section containing the words starting with the first letter of the desired word. From that section, we search for the words that contain the second letter of the desired word, and so on.

Example

Let’s understand this with the help of the following illustration:

Lexicographical order representation (with numbers comparison)

In the above example, we initially had a list of prime numbers: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}. After lexicographically arranging these numbers, the list becomes: {11, 13, 17, 19, 2, 23, 29, 3, 5, 7}.

Let’s have a look at another example to better understand this concept.

Lexicographical order representation, with a comparison

We have a list containing two words, {educative, educated}. We want to sort this list in lexicographical order. We’ll compare these two words letter by letter and sort these letters alphabetically. As a result, our list will become {educated, educative}.

Code

#include <iostream>
using namespace std;
int find_min(int * arr, int size) {
  //size must be greater than zero
  int min = arr[0];
  int temp = 0;
  for(int i = 1; i < size; i++) {
      temp = arr[i];
      while (temp / 10 != 0) {
        temp = temp / 10;
      }
      if (min > temp) {
        min = temp;
      }
  }
  return min;
}
int find_max(int * arr, int size) {
  //size must be greater than zero
  int max = arr[0];
  for(int i = 1; i < size; i++) {
      if (max < arr[i])
        max = arr[i];
  }
  
  return max;
}
void should_print(int number, int toCompare){
  int temp = number;
  while (temp / 10 != 0) {
     temp = temp / 10;
  }
  if(temp == toCompare) cout << number << " ";
}
void print_lexicographically(int * arr, int size) {
  int min = find_min(arr, size);
  int max = find_max(arr, size);
  int k;
  int val;
  while (min <= max) {
    for(int j = 0; j < size; j++){
        
      should_print(arr[j], min);
        
    }
    min += 1;
  } 
}
int main() {
  // your code goes here
  int arr[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
  print_lexicographically(arr, 10);
  return 0;
}

Note: The provided array or set must be totally ordered.

Explanation

  • Line 69: We declare an array of size 10 containing the following values: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}.
  • Line 70: We call the print_lexicographically() function and pass the array and its size as arguments.
  • Lines 48 and 49: We find minimum and maximum elements from the array to get the lower and upper range of values.
  • Line 54: We loop through the calculated range, and after each iteration, increment the min variable by 1 in line 61.
  • Line 55: We have an inner loop calling the should_print() function to print the sequence whose first digit matches the minimum value.
  • Line 36-43: In should_print(), we split the integer to get the first digit. We then check whether that digit matches the minimum value. If it does, then we print this digit.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved