C++ Online Compiler
Example: Postman Sort Algorithm in C++ in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// 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; }
Output
Clear
ADVERTISEMENTS