Alphabetize string with words and numbers

Question

I'm trying to figure out how to alphabetize a single string that contains both words and numbers. As you can see below, I've tried using isdigit but some of the numbers are negative so my code is always wrong. Also, my code splits the string into substrings which alphabetize separately, but I don't know how to alphabetize all of the words separately, put them back into their spots in the vector and then alphabetize all of the numbers separately, and put them back into their spots. Could someone help?

EDIT:

Sample input #1:

4 dog 1 -3 0 cat 3

Sample output #1:

-3 cat 0 1 3 dog 4

Sample input #2:

tom 4 0 9 kid pie 1

Sample output #2:

kid 0 1 4 pie tom 9

So far my code looks like this:

vector<string> numbers; 
string str;
string x;                   
getline (cin, str);
stringstream ss(str);
while (ss >> x){
   numbers.push_back(x);
}

if (numbers.size()==1){
    cout << numbers[0] << endl;
    return 0;
}

vector<int> results(numbers.size());
for (int i=0;i<numbers.size();i++){
    char *a=new char[numbers[i].size()+1];
    a[numbers[i].size()]=0;
    memcpy(a,numbers[i].c_str(),numbers[i].size());
    if(isdigit(*a)==0)
    {
        results[i]=1;
    } else{
        results[i]=0;
    }
}

int j=0;
while (j<numbers.size()){
    int k=j+1;
    while (k<numbers.size()){
        while (results[j]==results[k]){
            sort(numbers.begin()+j,numbers.begin()+k+1);
            k++;
        }
        j=k;
        k=numbers.size();
    }
    if(j==numbers.size()){
        for (int i=0; i<numbers.size();i++){
            cout << numbers[i] << " ";
        }
        j++;
    }
}

Answer 1

First you need a function that determines, whether a string is a number or not. Use strtol for this:

#include <stdlib.h> // strtol

bool is_number( const std::string &str, long &num )
{
    char *p;
    num = strtol( str.c_str(), &p, 10 );
    return *p == '\0';
}

Use this function in a second function, which determines whether string a is less than string b.

#include <tuple>

bool sortFunc( const std::string &a, const std::string &b )
{ 
    long numA;
    long numB;
    bool is_a_num = is_number( a, numA );
    bool is_b_num = is_number( b, numB );
    return std::make_tuple( !is_a_num, numA, a ) < std::make_tuple( !is_b_num, numB, b );                                      
}

Use std::sort, to sort the strings int the std::vector

// include <algorithm> // sort

std::vector< std::string > numbers;
.... 
std::sort( numbers.begin(), numbers.end(), sortFunc );

An other solution would be to split the vector in two separate vectors. One for strings and one for numbers and to sort them separately:

std::vector< std::string > numbers;
....
std::vector< std::string > vStr;
std::vector< long > vNum;
for ( std::string &str: numbers )
{
    long num;
    if ( is_number( str, num )
        vNum.push_back( num );
    else
        vStr.push_back( str);
}
std::sort( vNum.begin(), vNum.end() );
std::sort( vStr.begin(), vStr.end() );

Use a std::map if you want to know the position of each string or number in the original vector.

#include <map>

std::vector< std::string > numbers;
....
std::map< std::string, size_t > mapStr; // map string to index of string in vector numbers
std::map< long, size_t > mapNum;        // map number to index of number in vector numbers
for ( size_t index = 0; index < numbers.size(); index ++ )
{
    long num;
    if ( is_number( numbers[index], num ) )
        mapNum.emplace( num, index );
    else
        mapStr.emplace( numbers[index], index );
}

for ( auto & pa : mapNum )
    std::cout << pa.first << " pos " << pa.second << std::endl;
for ( auto & pa : mapStr )
    std::cout << pa.first.c_str() << " pos " << pa.second << std::endl;

Of course you can use a single std::map with a comparator function too:

std::vector< std::string > numbers;
....
std::map< std::string, size_t, bool(*)(const std::string &a, const std::string &b) > mapN( sortFunc );
for ( size_t index = 0; index < numbers.size(); index ++ )
    mapN.emplace( numbers[index], index );

for ( auto & pa : mapN )
    std::cout << pa.first << " pos " << pa.second << std::endl;

You can use std::tuple as key for the std::map too:

std::vector< std::string > numbers;
....
std::map< std::tuple< bool, long, std::string>, size_t > mapTupleN;
for ( size_t index = 0; index < numbers.size(); index ++ )
{
    long num;
    bool is_num = is_number( numbers[index], num );
    mapTupleN.emplace( std::make_tuple( !is_num, num, numbers[index] ), index );
}
for ( auto & pa : mapTupleN )
{
    if ( !std::get<0>(pa.first) )
        std::cout << std::get<1>(pa.first) << " is number at position " << pa.second << std::endl;
    else
        std::cout << std::get<2>(pa.first).c_str() << " is string at position " << pa.second << std::endl;
}