Working of sort() in c++ while sorting strings

Question

I was solving a problem, QuestionsLink, where we are given a name along with an integer. You have to print three names with the maximum integer values.

So, I converted the number to a string and concatenated it before the names. After sorting I was getting desired results. But it failed some test cases which made me curious about how the sort function in c++ works.

Here is my code:

#include <bits/stdc++.h>
#define ll long long int

using namespace std;

int main() {

  ll n;
  cin >> n;

  string names[n];
  int arr[n], digits[n];

  for (int i = 0; i < n; i++) {
    cin >> names[i] >> arr[i];
    names[i] = to_string(arr[i]) + names[i];
  }

  for (int i = 0; i < n; i++) {
    digits[i] = floor(log10(arr[i]) + 1);
  }

  sort(names, names + n, greater<string>());

  for (int i = 0; i < n; i++) {
    cout << names[i] << endl;
  }
  /*for(int i=0;i<3;i++){
     string s = names[i].substr(digits[i],names[i].length());
     cout<<s<<endl;
   }
   cout<<digits[98];
 */
  return 0;
}

Test cases:

9huDmy
995YnAYoAEE
990RUTM
96ipORo
956LNjFa

So, After sorting in descending order how is 9huDmy on top while the next two are sorted based on the digits in front of them.

The ASCII code of `'h'` (104) is bigger than the ASCII code of `'9'` (57) or of any other digit. That's why. — DYZ, Feb 23 '20 at 19:24
Don't use `#include ` ([Why should I not #include ?](https://stackoverflow.com/questions/31816095)), using low letter defines (`#define ll long long int`) can lead to many unexpected problems, use `using` instead (`using ll = unsigned long long;`). Dynamic size array (`string names[n]`) are not standard c++ but an extension use std containers instead. — t.niese, Feb 23 '20 at 19:43
I would like to expand in @T.niese: Don't use the "competitive coding" environment for learning a language (any language). Competitive coding optimizes in all the wrong places, and DE-emphasizes those things you would WANT in a "real" program -- readability, maintainability, modularity. — DevSolar, Feb 24 '20 at 07:40

DevSolar · Accepted Answer · 2020-02-23T20:29:18.620

Because greater<string> sorts numbers as smaller than characters, based on their ASCII value.

You shouldn't've concatenated them in the first place.

1) Use std::pair< int, std::string > to group integers and strings.

2) Use std::vector< std::pair< int, std::string > >, not C arrays.

3) ~~Write a comparator functor (or lambda) that sorts pairs depending on their int value.~~ Comparing std::pair automatically compares their .first element, i.e. your integer values.

4) Use verbose std::, or using std::string etc, not using namespace ..., as your global namespace will get awfully crowded very fast.

Working of sort() in c++ while sorting strings

1 Answers1