Segment sorting

Question

This is a question from careercup.com. You are given an alphanumeric string. Complete the function sortSegments that will segment the string into substrings of consecutive letters or numbers and then sort the substrings. For example, the string "AZQF013452BAB" will result in "AFQZ012345ABB". The input letters will be uppercase and numbers will be between 0 and 9 inclusive.

#include <iostream>
#include <string>
#include <algorithm>
void sortSegments(std::string& input)
{
 bool toggle1 = isalpha(input[0])? true: false;
 size_t k = 0;
 for(size_t i = 1; i <= input.size(); ++i)
 {
 bool toggle2 = isalpha(input[i])? true: false;
 if(toggle1 != toggle2)
 {
 std::sort(input.begin()+k, input.begin()+i);
 toggle1 = toggle2;
 k=i;
 }
 }
}
int main()
{
 std::string input("AZQKF013452BAB");
 sortSegments(input);
 std::cout << input;
}

• Artemy Vysotsky: As style only improvement - you can make your function to return reference to input to allow calls chaining std::cout << sortSegments(input) << '\n';

Answer 1

FWIW, your function has a bug.

If you change the input string to "AZQKF013452BAB98", you will notice the problem.

The reason for the bug it that the null character is neither a digit nor an alphabetical character.

Here's an updated version of the function that fixes the bug.

void sortSegments(std::string& input)
{
 bool toggle1 = isalpha(input[0])? true: false;
 size_t k = 0;
 // Change the <= to <
 for(size_t i = 0; i < input.size(); ++i)
 {
 bool toggle2 = isalpha(input[i])? true: false;
 if(toggle1 != toggle2)
 {
 std::sort(input.begin()+k, input.begin()+i);
 toggle1 = toggle2;
 k=i;
 }
 }
 // Sort the remaining characters.
 std::sort(input.begin()+k, input.end());
}

• Artemy Vysotsky: Why do you need i outside the loop? it should be equal to input.size() when loop exits, or just pass input.end(). I would rewrite it using iterators from the beginning
• R Sahu: @ArtemyVysotsky, good point.
• Artemy Vysotsky: your fix is not good - choose begin()+size() or end(). Just size() will not compile