#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <regex>
using namespace std;
// Custom comparison function for natural sorting
bool natural_compare(const string &a, const string &b) {
// Regular expression to split the string into numeric and non-numeric parts
regex re("(\\D+)|(\\d+)");
auto a_parts = sregex_token_iterator(a.begin(), a.end(), re, {1, 2});
auto b_parts = sregex_token_iterator(b.begin(), b.end(), re, {1, 2});
// Iterate through both string parts
while (a_parts != sregex_token_iterator() && b_parts != sregex_token_iterator()) {
string part_a = *a_parts++;
string part_b = *b_parts++;
// Compare the parts: if they are numbers, compare as integers, otherwise lexicographically
if (isdigit(part_a[0]) && isdigit(part_b[0])) {
int num_a = stoi(part_a);
int num_b = stoi(part_b);
if (num_a != num_b) return num_a < num_b;
} else if (part_a != part_b) {
return part_a < part_b;
}
}
// If all parts are the same, the strings are equal
return a_parts != sregex_token_iterator();
}
void natural_sort(vector<string>& vec) {
sort(vec.begin(), vec.end(), natural_compare);
}
int main() {
// Sample strings
vector<string> strings = {"Space Force 1", "Space Force 01", "Space Force 2", "Space Force 11", "Space Force 10"};
// Perform natural sort
natural_sort(strings);
// Print sorted result
for (const string &str : strings) {
cout << str << endl;
}
return 0;
}