Will std::sort always compare equal values?

user_72178 0
Viewed 232

I am doing the following problem on leetcode: https://leetcode.com/problems/contains-duplicate/

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

The solution I came up to the problem is the following:

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        try {
            std::sort(nums.begin(), nums.end(), [](int a, int b) {
                if (a == b) {
                    throw std::runtime_error("found duplicate");
                }
                return a < b;
            });
        } catch (const std::runtime_error& e) {
            return true;
        }
        
        return false;
    }
};

It was accepted on leetcode but I am still not sure if it will always work. The idea is to start sorting nums array and interrupt as soon as duplicate values are found inside comparator. Sorting algorithm can compare elements in many ways. I expect that equal elements will be always compared but I am not sure about this. Will std::sort always compare equal values or sometimes it can skip comparing them and therefore duplicate values will not be found?

algorithm c++
1 Answers

Will std::sort always compare equal values or sometimes it can skip comparing them and therefore duplicate values will not be found?

Yes, some equal value elements will always be compared if duplicates do exist.

Let us assume the opposite: initial array of elements {e} for sorting contains a subset of elements having the same value and a valid sorting algorithm does not call comparison operator < for any pair of the elements from the subset.

Then we construct same sized array of tuples {e,k}, with the first tuple value from the initial array and arbitrary selected second tuple value k, and apply the same sorting algorithm using the lexicographic comparison operator for the tuples. The order of tuples after sorting can deviate from the order of sorted elements {e} only for same value elements, where in the case of array of tuples it will depend on second tuple value k.

Since we assumed that the sorting algorithm does not compare any pair of same value elements, then it will not compare the tuples with the same first tuple value, so the algorithm will be unable to sort them properly. This contradicts our assumptions and proves that some equal value elements (if they exist in the array) will always be compared during sorting.

user_73255990
Related