C++ Program to Sort Elements in Lexicographical Order (Dictionary Order)

Introduction

Sorting elements in lexicographical order, often called dictionary order, involves arranging items such that their string representations follow the order seen in dictionaries. This is a common task in software development, especially when dealing with large data sets that require orderly representation for ease of searching and display.

In this article, you will learn how to sort elements in lexicographical order using C++. You'll explore various examples to demonstrate sorting of strings, integers, and custom objects, ensuring you grasp the nuances of implementing efficient sorting mechanisms in different scenarios.

Sorting Strings in Lexicographical Order

Sorting Simple Strings

1. Include the necessary headers from the C++ Standard Library.

2. Initialize a vector of strings.

3. Use the Standard Template Library (STL) sort function from the <algorithm> header.

4. Display the sorted strings.

   cpp Copy

   #include <iostream>
   #include <vector>
   #include <algorithm>
   
   int main() {
       std::vector<std::string> words = {"Banana", "Apple", "Cherry", "Date"};
       std::sort(words.begin(), words.end());
   
       for(const auto& word : words) {
           std::cout << word << std::endl;
       }
       return 0;
   }
   

   This code snippet initializes a vector containing several fruit names and sorts them in lexicographical order. The std::sort() function rearranges the items in the words vector from 'Apple' to 'Date', ensuring alphabetical order.

Sorting Case-insensitive

1. Take into account upper and lowercase letters which might affect regular string sorting.

2. Transform all strings to a standard case before sorting.

3. Use the std::transform() function in combination with std::sort().

   cpp Copy

   #include <iostream>
   #include <vector>
   #include <algorithm>
   #include <cctype>
   
   // Function to convert string to lowercase
   std::string toLower(std::string data) {
       std::transform(data.begin(), data.end(), data.begin(),
           [](unsigned char c){ return std::tolower(c); });
       return data;
   }
   
   int main() {
       std::vector<std::string> words = {"banana", "Apple", "cherry", "date"};
       std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) {
           return toLower(a) < toLower(b);
       });
   
       for(const auto& word : words) {
           std::cout << word << std::endl;
       }
       return 0;
   }
   

   Here, the sorting function utilizes a lambda that converts each string to lowercase using the toLower function before comparing them. This approach avoids issues related to case sensitivity, ensuring that 'Apple' sorts before 'banana' despite capitalization.

Sorting Other Data Types

Sorting Numeric Types

1. Recognize that sorting numbers in lexicographical order treats them as strings.

2. Convert numbers to strings, then sort those strings.

3. Re-convert strings to numbers if necessary.

   cpp Copy

   #include <iostream>
   #include <vector>
   #include <algorithm>
   #include <string>
   
   int main() {
       std::vector<int> numbers = {202, 30, 54, 1};
       std::vector<std::string> numStrs;
   
       for(const auto& num : numbers) {
           numStrs.push_back(std::to_string(num));
       }
   
       std::sort(numStrs.begin(), numStrs.end());
   
       for(const auto& str : numStrs) {
           std::cout << std::stoi(str) << std::endl;
       }
       return 0;
   }
   

   The code converts a list of integers into strings, sorts them lexicographically, and then converts them back to integers for display. It ensures numbers such as '202' appear before '30', as per dictionary order of their string forms.

Conclusion

Sorting elements in lexicographical order in C++ is a versatile skill that enhances your ability to manage and display data effectively. Whether working with simple strings, handling varied case sensitivities, or sorting numeric values as strings, the examples provided equip you with the necessary tools to implement robust sorting functions. Apply these techniques in your projects to ensure data is presented cleanly and logically, enhancing usability and readability.