Sorting Std::Strings with Numbers in Them

Sorting std::strings with numbers in them?

You can create a custom comparison function to use with std::sort. This function would have to check if the string begins with a numeric value. If it does, convert the numeric part of each string to an int using some mechanism like a stringstream. Then compare the two integer values. If the values compare equally, compare the non-numeric part of the strings lexicographically. Otherwise, if the strings don't contain a numeric part, simply compare the two strings lexicographically as normal.

Basically, something like the following (untested) comparison function:

bool is_not_digit(char c)
{
    return !std::isdigit(c);
}

bool numeric_string_compare(const std::string& s1, const std::string& s2)
{
    // handle empty strings...

    std::string::const_iterator it1 = s1.begin(), it2 = s2.begin();

    if (std::isdigit(s1[0]) && std::isdigit(s2[0])) {
        int n1, n2;
        std::stringstream ss(s1);
        ss >> n1;
        ss.clear();
        ss.str(s2);
        ss >> n2;

        if (n1 != n2) return n1 < n2;

        it1 = std::find_if(s1.begin(), s1.end(), is_not_digit);
        it2 = std::find_if(s2.begin(), s2.end(), is_not_digit);
    }

    return std::lexicographical_compare(it1, s1.end(), it2, s2.end());
}

And then...

std::sort(string_array.begin(), string_array.end(), numeric_string_compare);

EDIT: Of course, this algorithm is only useful if you're sorting strings where the numeric portion appears at the beginning of the string. If you're dealing with strings where the numeric portion can appear anywhere in the string, then you need a more sophisticated algorithm. See http://www.davekoelle.com/alphanum.html for more information.

How can i sort a string with integers in c++?

Here it's done with std::sort from the header algorithm

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

int main(){

    std::vector<std::string> nums{
        "922003001020293839297830207344987344973074734",
        "766352786207892397340783784078348747606208602",
        "182823068326283756515117829362376823572395775"
    };

    std::cout << "unsorted: " << std::endl;
    for (auto i : nums){
        std::cout << i << std::endl;
    }

    std::sort(nums.begin(), nums.end()); //sort it

    std::cout << "\nsorted: " << std::endl;
    for (auto i : nums){
        std::cout << i << std::endl;
    }

    system("pause");
    return 0;
}

output:

unsorted: 
922003001020293839297830207344987344973074734
766352786207892397340783784078348747606208602
182823068326283756515117829362376823572395775

sorted: 
182823068326283756515117829362376823572395775
766352786207892397340783784078348747606208602
922003001020293839297830207344987344973074734

Sorting string array with numbers C++

First, if you allocate memory with operator new, you must release it with operator delete[].

Second, when you sort strings instead of values, they are sorted just like strings would do, and here is where your problem lies. You see, 100 is alphabetically less than 2 or 20, that's why it would appear earlier.

Here's the output your program gives. Check this rule out, and you'll see that i'm right.

10 100 110 120 130 140 150 160 20 30 40 50 60 70 80 90

Third, using operator new is discouraged for pretty much anything. You have STL, and you seem to be using it extensively - why not vector?

Fourth, you don't check if anything we write into numbers[i] is actually a number. Think on that.

Fifth, for N being long enough(more than 2^sizeof(size_t)) your problem will NEVER stop due to integer overflow.

Sixth, you don't check for n == 0, and you will ultimately get memory access violation if you enter it.

A fast-right-off-the-bat fix for your problem:

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int main() {
    int examples;
    cin >> examples;
    for (size_t i = 0; i < examples; i++)
    {
        size_t n;
        cin >> n;
        if (n <= 0)
            break;
        vector<string> numbers(n);
        for (size_t i = 0; i < n; i++)
            cin >> numbers[i];

        //here we add a predicate for string checking,
        //which evaluates the length of string
        //before using the usual operator<.

        sort(begin(numbers), end(numbers), [](const string& s1, const string& s2){
            if (s1.length() < s2.length())
                return true;
            if (s2.length() < s1.length())
                return false;
            else
                return (s1 < s2);
        });

        if (n % 2 == 0) {
            cout << numbers[n / 2 - 1];
        }
        else
            cout << numbers[n / 2];
    }

    system("pause");
    return 0;
}

Still, it has a number of problems:

1. Checking if numbers[i] is actually a number

2. I'm not sure that
   predicate I wrote doesn't have bugs - I'm just trying to give you
   the idea of how it should work.

Sorting vectors of string containing both numbers and words

std::sort allows an optional comparator. A simple lambda function allows you to perform basic manipulations to compare based on different components of the string. Here's a really simple minimal example that assumes the course numbers are always three digits long, followed by a space, so you can just use std::stoi for the numeric comparison, and the substr method for the course title comparison:

int main()
{
    std::vector<std::string> title{"202 Physics"s, "101 Math"s, "303 Chemistry"s};

    std::sort(title.begin(), title.end(), [](const auto& a, const auto &b) { return std::stoi(a) < std::stoi(b); });

    std::cout << "By number" << std::endl;
    for (auto&& s : title) {
        std::cout << s << std::endl;
    }

    std::sort(title.begin(), title.end(), [](const auto& a, const auto &b) { return a.substr(4) < b.substr(4); });
    std::cout << std::endl << "By title" << std::endl;
    for (auto&& s : title) {
        std::cout << s << std::endl;
    }
    return 0;
}

Try it online!

In each case, the comparator returns true when the left element is less than the right, so [](const auto& a, const auto& b) { return std::stoi(a) < std::stoi(b); }) is converting both strings to int (std::stoi stops processing when it hits the non-numeric space character after the course number) and comparing, while [](const auto& a, const auto &b) { return a.substr(4) < b.substr(4); } is slicing off the first four characters of each string, leaving only the course titles, and comparing the remainder.

How to sort string array by number if the string contains numbers and characters c++

You can't use just one big string because 604 James Jones is lexicographically larger than 5516 Example Name. The first character of 604, 6, is greater than the 5 of 5516 in spite of 5516 being a larger number than 604.

Rather than an array of strings, I'd use a container, probably a std::vector, of a score structure. score would contain the score (possibly an int), the name (a string), and an operator< that could be used to arrange scores by their scores. Something like

struct score
{
    int mScore;
    std::string mName;
    bool operator<(const score & other)
    {
        return mScore < other.mScore;
    }
};

When parsing the file into the structure, use option 2 of this answer as inspiration.

You can then use std::sort from the algorithm library to sort the container.

Sorting strings with numerical digits in it

Since the character encoded values of numerals are ordered in the same order as the numbers they represent, you can do string comparison on the last four digits:

#include <cstring>
#include <string>

// Requires: a.size() >= 2, b.size() >= 2
bool two_less(std::string const & a, std::string const & b)
{
    return std::strcmp(a.data() + 2, b.data() + 2) < 0;
}

Now use sort with predicate:

#include <algorithm>
#include <vector>

std::vector<std::string> data { "7X1234", "YX1236" };

std::sort(data.begin(), data.end(), two_less);

---

In C++11, and in particular if you have no repeated use for this, you can also use a lambda directly in the sort call:

std::sort(data.begin(), data.end(),
         [](std::string const & a, std::string const & b)
         { return std::strcmp(a.data() + 2, b.data() + 2) < 0; });

Then you can even make the number "2" a captured variable if you need to vary it.

Sorting strings containing numbers in a user friendly way

Jeff wrote up an article about this on Coding Horror. This is called natural sorting, where you effectively treat a group of digits as a single "character". There are implementations out there in every language under the sun, but strangely it's not usually built-in to most languages' standard libraries.

---

Related Topics