CODEWITHSUNDEEP
c++arraysstringsortingvector
sunidhi chaudhary
sunidhi chaudhary

Reputation: 31

Failing to sort my array with std::sort and custom comparator

arr.push_back("1"); 
arr.push_back("34"); 
arr.push_back("3"); 
arr.push_back("98"); 
arr.push_back("9"); 
arr.push_back("76"); 
arr.push_back("45"); 
arr.push_back("4"); 

sort(arr.begin(), arr.end(), myCompare); 

//Here is the compare function
int myCompare(string X, string Y) 
{ 
  string XY = X.append(Y); 

  string YX = Y.append(X); 
  return XY.compare(YX) > 0 ? 1: 0; 
} 
//output should be 998764543431

I got some confusion regarding the sorting for eg. we have numbers {"1","34","3","98","9","76","45","4"}. When we first compare 2 strings we have 2 options 134 and 341 so as 341 is bigger we'll get 341 as a returned string.

Similarly, we get 3341 in next iteration and 983341 in next and 9983341 in next but when 76 arrives it has to be appended either at the beginning or at the end either it will 998334176 or 769983341 which is wrong. Am I missing something?

Upvotes: 1

Views: 94

Answers (1)

3Dave
3Dave

Reputation: 29051

There are a few issues. Ignoring the questions of why you're storing int as std::string? This only makes sense if you'll be storing non-integer data in the array at some point. Integer comparison is very fast. string comparison is slow and almost never produces the desired result.

First,

std::string::append modifies the parameter. So, if I have:

string x = "left";
string y = "right";
string xy = x.append(y);

x now equals "leftright", as does xy. Your comparison function would append x to y, then y to the result.

Your method, called with X = 1, Y = 34:

string XY = X.append(Y); 
// XY = "134", X = "134", Y = "34"
string YX = Y.append(X); 
// YX = 34134, Y = "34134", X = "134"

return XY.compare(YX) > 0 ? 1: 0;

So, this could be expressed as 

X = X + Y;
XY = X;
Y = Y + X;
YX = Y;

string::compare does a character compare. So, if your array were sorted just using string::compare, you'd get

1       3       34      4       45      76      9       98

Second,

When we first compare 2 strings we have 2 options 134 and 341 so as 341 is bigger we'll get 341 as a returned string.

"341" is bigger than "134". However, you aren't comparing "341" with "134" - you're comparing "134" with "3134". "3134" is only bigger because it starts with a 3 instead of a "1". If the numbers were "1341" and "341", "341" would still be bigger.

If your goal is just to sort the list based on integer value,

int myCompare(string X, string Y)
{
    return atoi(X.c_str()) < atoi(Y.c_str());
}

Or, more sanely, use an int array instead of strings, and let sort use it's built-in comparison function.

Upvotes: 1

Related Questions