Example: Postman Sort Algorithm in C++ in C++

// Postman Sort Algorithm in C++
#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // For std::max

// Function to get the maximum length of strings in the array
// This determines the number of passes needed for Radix Sort.
int getMaxLength(const std::vector<std::string>& arr) {
    int maxLength = 0;
    for (const std::string& s : arr) {
        maxLength = std::max(maxLength, (int)s.length());
    }
    return maxLength;
}

// A stable counting sort for characters at a specific index
// This function sorts the 'arr' based on the character at 'char_index'.
// Shorter strings are effectively 'padded' with a null character (0) for sorting.
void countingSortByChar(std::vector<std::string>& arr, int char_index) {
    const int RANGE = 256; // ASCII character range (0-255)
    int n = arr.size();
    std::vector<std::string> output(n);
    std::vector<int> count(RANGE, 0);

    // Store count of occurrences of characters at char_index
    // If char_index is out of bounds for a string, treat it as null character (0)
    for (int i = 0; i < n; i++) {
        char c = (char_index < arr[i].length()) ? arr[i][char_index] : 0;
        count[c]++;
    }

    // Change count[i] so that count[i] now contains the actual
    // position of this character in the 'output' array.
    for (int i = 1; i < RANGE; i++) {
        count[i] += count[i - 1];
    }

    // Build the output array. Iterate from the end to ensure stability.
    for (int i = n - 1; i >= 0; i--) {
        char c = (char_index < arr[i].length()) ? arr[i][char_index] : 0;
        output[count[c] - 1] = arr[i];
        count[c]--;
    }

    // Copy the output array to arr, so that arr now contains strings
    // sorted according to the current char_index.
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// The main function to perform Postman Sort on a vector of strings.
// It orchestrates multiple passes of counting sort.
void postmanSort(std::vector<std::string>& arr) {
    int maxLen = getMaxLength(arr);

    // Perform counting sort for every character position, starting from the
    // last character (least significant digit) and moving to the first character
    // (most significant digit).
    for (int char_index = maxLen - 1; char_index >= 0; char_index--) {
        countingSortByChar(arr, char_index);
    }
}

int main() {
    // Step 1: Initialize an array of strings (e.g., city names or addresses).
    std::vector<std::string> addresses = {"NYC", "LA", "SF", "BOSTON", "CHICAGO", "DALLAS", "HOUSTON", "MIAMI"};

    std::cout << "Original list of addresses:" << std::endl;
    for (const std::string& s : addresses) {
        std::cout << s << " ";
    }
    std::cout << std::endl;

    // Step 2: Apply Postman Sort to the list of strings.
    postmanSort(addresses);

    // Step 3: Display the sorted list to verify the algorithm's correctness.
    std::cout << "\nSorted list of addresses:" << std::endl;
    for (const std::string& s : addresses) {
        std::cout << s << " ";
    }
    std::cout << std::endl;

    return 0;
}