JohnSmithEr JohnSmithEr - 17 days ago 4
C++ Question

Sorting string array with numbers C++

I have problem solving this problem.
The task is simple at first line I enter how many examples I have.
On second line I need to enter how many numbers im going to read.
and then we enter all the numbers separate by space.
The task itselfs do , sorting the string array wtih numbers from smalles to the biggest one. After that if we have even numbers entered we print the middle number -1, if they are uneven we just print the middle number.

So far if I use the exact same code with long long it works perfectly , but it is limited only to 19 digit number and I want to expand the program so it can use bigger numbers.

Using that way the sort func , when I try to sort 16 elements from 160 to 10 , they all messed it start from 110 then in the midle is 160 and so one , which makes absolutly non sense, using 5 numbers or 8 works perfectly w/o any problem , using more numbers fails.

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

using namespace std;




int main() {
int examples;
cin >> examples;
for (size_t i = 0; i < examples; i++)
{
long long unsigned int n;
cin >> n;
string * numbers = new string[n];
for (size_t i = 0; i < n; i++)
{
cin >> numbers[i];
}

sort(numbers, numbers + n);

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



}

system("pause");
return 0;
}

Answer

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(numbers.begin(), numbers.end(), [](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.