Sorting a 2-d vector but getting an unexpected output-CodePudding

I am trying to sort a 2 D vector and I am getting the desired output for input 'n' less than 15 but above that it is not arranged in the order that I want. If all the first column values are 0 then the second column must have increasing ordered values.

#include <bits/stdc  .h>
using namespace std;
bool sortcol(const vector<long long int>& v1, const vector<long long int>& v2)
{
    return v1[0] < v2[0];
}
int main()
{
    int n;
    cin >> n;
    
    vector<vector<long long int>> arr(n,vector<long long int> (2));
    
    for (int i = 0; i < n; i  )
    {
         arr[i][0] = 0;
         arr[i][1] = i;
    }
    
    
    sort(arr.begin(), arr.end(),sortcol);
    for(int i = 0;i<n;i  ){
        cout << i << " - " << arr[i][0] << " , " << arr[i][1] << endl;
    }
}

Output I want to be like :-

15 0
0 - 0 , 0
1 - 0 , 1
2 - 0 , 2
3 - 0 , 3
4 - 0 , 4
5 - 0 , 5
6 - 0 , 6
7 - 0 , 7
8 - 0 , 8
9 - 0 , 9
10 - 0 , 10
11 - 0 , 11
12 - 0 , 12
13 - 0 , 13
14 - 0 , 14

But what I getting is :-

50 0
0 - 0 , 38
1 - 0 , 26
2 - 0 , 27
3 - 0 , 28
4 - 0 , 29
5 - 0 , 30
6 - 0 , 31
7 - 0 , 32
8 - 0 , 33
9 - 0 , 34
10 - 0 , 35
11 - 0 , 36
12 - 0 , 37
13 - 0 , 25
14 - 0 , 39
15 - 0 , 40
16 - 0 , 41
17 - 0 , 42
18 - 0 , 43
19 - 0 , 44
20 - 0 , 45
21 - 0 , 46
22 - 0 , 47
23 - 0 , 48
24 - 0 , 49
25 - 0 , 13
26 - 0 , 1
27 - 0 , 2
28 - 0 , 3
29 - 0 , 4
30 - 0 , 5
31 - 0 , 6
32 - 0 , 7
33 - 0 , 8
34 - 0 , 9
35 - 0 , 10
36 - 0 , 11
37 - 0 , 12
38 - 0 , 0
39 - 0 , 14
40 - 0 , 15
41 - 0 , 16
42 - 0 , 17
43 - 0 , 18
44 - 0 , 19
45 - 0 , 20
46 - 0 , 21
47 - 0 , 22
48 - 0 , 23
49 - 0 , 24

I am running this code on VS code

CodePudding user response：

As others have also noted in the comments, your sortcol() always returns false because v1[0] and v2[0] are always 0. Since the predicate sortcol() tells the sorting algorithm which elements are considered to be "smaller"/"less" than other elements, no element is considered smaller than another one. This implies that all elements are considered to be equal: If a<b is false and b<a is false, this implies a==b is true. In other words, the STL sorting algorithms assume a strict weak ordering, compare e.g. this post and this one.

So all your elements are considered to be equal by the sorting algorithm. The order of elements considered to be equal is implementation defined for std::sort(). Quote for std::sort:

The order of equal elements is not guaranteed to be preserved.

Hence, in your case the implementation is free to change the order of all elements as it sees fit, since all elements are considered to be equal. In practice a different algorithm is used once the input reaches a certain size, in which case a different algorithm is selected. For libstdc (the STL of gcc), this happens for n>16 (see the constant _S_threshold in the source code). That is the reason why you see a jump in behavior for n>16 with std::sort(). Other implementations of the STL might use other thresholds (e.g., the Microsoft STL seems to use a value of 32).

On the other hand, std::stable_sort() guarantees that the order of equal elements remains the same. Quote for std::stable_sort:

The order of equivalent elements is guaranteed to be preserved.

Of course, preserving the order is not free, and hence std::stable_sort can be slower.

So, if your sortcol() is really the predicate you want (although, in the example, it does not really make much sense), using std::stable_sort() is the solution you are look for.