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:

#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.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

What is a lexicographic order?

Overview

Example

Code

Explanation