Sorting a 2-d vector but getting an unexpected output

Question

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

All of your `arr[i][0]` values are in fact, `0`. Any/every order is allowable; as far as `sort` is concerned they are **all** value-equivalent. If you want sub-ordering you need to account for it in the comparator, and make *sure* it is strict-weak compliant. — WhozCraig, Apr 07 '22 at 18:47
`std::vector` already defines `operator<` (well, technically `operator<=>` now, which can stand in for `operator<`). Sounds like you should just let `sort` do its thing without providing your own comparison class. Edit: https://godbolt.org/z/Me6of6G9G — AndyG, Apr 07 '22 at 19:19
Your `sortcol()` always returns `false` because the `v1[0]` and `v2[0]` are both always 0. The order of elements which compare equal is not preserved by `std::sort`. Maybe you are looking for `std::stable_sort()`? — Sedenion, Apr 07 '22 at 19:27
you should start with smaller input and be more clear on how you want to have them ordered. Your code just applies the sorting according to your comparator — 463035818_is_not_an_ai, Apr 07 '22 at 19:30
@Sedenion that worked , but I am still wondering as why different outputs . if the problem lies in sortcol then why it worked for n = 15 — Aryaman, Apr 08 '22 at 09:06

score 1 · Accepted Answer · answered Apr 08 '22 at 10:37

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.

Sorting a 2-d vector but getting an unexpected output

1 Answers1