getting segmentation fault in recursive insertion sort-CodePudding

I was trying to write recursive code of insertion sort, but i am getting segmentation fault. please help me with this.

#include <bits/stdc  .h>

using namespace std;

void insert(vector<int> &v,int temp){
    if(v.size()==0||v[v.size()-1]<=temp){
        v.push_back(temp);
        return;
    }
    int val = v[v.size()-1];
    v.pop_back();
    insert(v, temp);
    v.push_back(val);
    return;
}

void sort(vector<int> &v){
    if(v.size()==1) return;
    int temp = v[v.size()-1];
    v.pop_back();
    sort(v);
    insert(v,temp);
}

int main() {
    int n;
    vector<int> v;
    cin>>n;
    for(int i=0;i<n;i  )
    cin>>v[i];
    sort(v);
    for(int i=0;i<n;i  )
    cout<<v[i];
    return 0;
}

CodePudding user response：

The problem is that the vector v is empty(meaning it has size 0) and you're trying to access its elements which leads to undefined behavior.

vector<int> v; //this creates an empty vector named v
cin>>n;
for(int i=0;i<n;i  )
cin>>v[i]; //this leads to undefined behavior

In the above snippet, the vector v is an empty vector meaning it has no elements. So the expression cin >> v[i], leads to undefined behavior because you're accessing elements at ith index of the vector but there are no elements inside the vector to access.

Undefined behavior means anything¹ can happen including but not limited to the program giving your expected output. But never rely(or make conclusions based) on the output of a program that has undefined behavior.

So the output that you're seeing(maybe seeing) is a result of undefined behavior. And as i said don't rely on the output of a program that has UB. The program may just crash(which is what happens in your case).

So the first step to make the program correct would be to remove UB. Then and only then you can start reasoning about the output of the program.

Solution

To solve this you can specify the size of the vector when creating it as shown below:

int n;
cin>>n;
vector<int> v(n);//create vector of size n

^{¹For a more technically accurate definition of undefined behavior see this where it is mentioned that: there are no restrictions on the behavior of the program.}

CodePudding user response：

This creates an empty vector<int>:

vector<int> v;

Accessing any elements in it will make your program have undefined behavior. You can instead create the vector<int> with the number of elements you want by supplying n to the constructor, or by calling resize(n) after creating an empty vector<int>. Other option is to create it empty, and then to push_back() or emplace_back elements into it in which case it'll grow dynamically.

Example creating it with the correct number of elements:

int main() {
    int n;

    // verify that extraction of `n` succeeded and that `n > 0`:
    if(!(std::cin >> n && n > 0)) {
        std::cerr << "error\n";
        return 1;
    }

    // create the vector with the correct number of elements
    std::vector<int> v(static_cast<size_t>(n));

    // use a range-based for loop to get a reference to each element:
    for(int& val : v)
        std::cin >> val;    // extract into the referenced `int`

    sort(v);

    // here you can use a range-based for loop to get a copy of each element
    // (which is cheap in this case, since they are `int`s):
    for(int val : v)
       std::cout << val << ' ';
    std::cout << '\n';
}

Demo

Notes:

#include <bits/stdc .h> - Never include this non-standard header. Include the standard headers, like iostream and vector
using namespace std; - Don't do this. Especially not when you provide overloads for functions like sort that will be available if you include bits/stdc .h and do using namespace std;.