How to sort array of strings which contains both negative and positive numbers in c++.?

user_11976978 0
Viewed 785
String str[]={"-123","89","-10","456"};

str is an array of strings, with each string in the format of an integer, and you have to perform sorting on this array in O(n log n) time.

The strings in str can represent both positive and negative integers. The maximum length of these strings is 1024 characters.

I know one solution of this problem is to convert the strings into numbers, then compare them apart from this; is there any other solution to this problem?

sorting arrays algorithm c++ string
2 Answers

Another solution is to implement your own comparison function:

  • Check the first character of both strings. If one starts with a digit and the other starts with a -, then the string that starts with - is the smaller number.
  • If both strings start with a digit, then compare the length of the strings. The shorter string is the smaller number. If both strings are the same length, perform a standard string compare.
  • If both strings start with -, then compare the length of the strings. The longer string is the smaller number. If both strings are the same length, perform a standard string compare, but negate the result.
user_33861090

Here's a minimal and potentially insufficient (doesn't handle leading zeroes, whitespace, etc.) example that does what you'd like.

The comments explain what it's doing. :)

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

int main() {
  std::vector<std::string> strings = {
      "-1", "-1", "-20", "-4", "3", "0", "-0", "1", "20", "20", "44020",
  };

  // Assumes everything in "strings" has no whitespace in it.
  // Assumes everything in "strings" does not have leading zeroes.
  // Assumes everything in "strings" is an ascii representaion of an integer.
  // Assumes everything in "strings" is nonempty.
  std::sort(strings.begin(), strings.end(),
            [](const std::string &a, const std::string &b) {
              const bool a_is_negative = a[0] == '-';
              const bool b_is_negative = b[0] == '-';
              if (a_is_negative != b_is_negative) {
                // If they have different signs, then whichever is negative is
                // smaller.
                return a_is_negative;
              } else if (a.length() != b.length()) {
                // If they have the same sign, then whichever has more
                // characters is larger in magnitude. When the sign is negative,
                // the longer (more digits) number is "more negative". When
                // positive, the longer (more digits) number is "more positive".
                return (a.length() < b.length()) != a_is_negative;
              } else {
                // Otherwise a lexicographic comparison of "a" and "b" will
                // determine which string is larger in magnitude. Using the same
                // logic above, we account for the "negative vs. positive"
                // comparison.
                return (a < b) != a_is_negative;
              }
            });

  for (const auto &str : strings) {
    std::cout << str << " ";
  }
  std::cout << std::endl;
}
user_28991620
Related