CODEWITHSUNDEEP
c++sortingsegmentation-fault
AlexM
AlexM

Reputation: 55

HackerRank Big Sorting segmentation Fault in C++

I have a question about the BigSorting task from HackerRank.

My code successfully runs all tests except 3. (I located files on which my program does not work under the names input03.txt, input04.txt and input05.txt on my google drive. Here is the link to the drive.) https://drive.google.com/drive/u/1/folders/1psno2RbeYXX5ohHjs5BWke6E-K2cJl-3

My program crashes with a "Segmentation fault" error. I’ve been sitting for 2 hours and can’t understand what the mistake is. This is my first question on StackOverflow, so I apologize right away if I did something wrong.

Here is the code. 

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

bool isShorter(const std::string& s1, const std::string& s2)
{
    if (s1.size() != s2.size())
    {
        return s1.size() < s2.size();
    }
    else
    {
        for (int i = 0; i < s1.size(); ++i)
        {
            int x = s1[i] - '0';
            int y = s2[i] - '0';
            if (x != y)
            {
                return x < y;
            }
        }
    }   
    return true;
}

std::vector<std::string> bigSorting(std::vector<std::string> unsorted) 
{
    std::sort(unsorted.begin(), unsorted.end(), isShorter);
    return unsorted;
}

Upvotes: 1

Views: 235

Answers (1)

walnut
walnut

Reputation: 22162

The function given to std::sort is supposed to induce a strict weak ordering on the elements in the iterator range, see std::sort, Compare requirements and strict weak ordering on wikipedia.

Your isShorter induces an order that is not strict. In particular it does not have the property that isShorter(x, x) == false for all x.

The problem is that you return true when you cannot find either string to come before or after the other in the order, but you should return false.

The function is supposed to model <, not <=.

Whether this is the cause of the segmentation fault is unclear since you haven't given a full code example, but violating the std::sort requirements does cause undefined behavior.

Upvotes: 3

Related Questions