Segmentation fault with cout in merge sort

Question

I've read many posts but I can't figure out where is my error so I go with it. My program throws the segfault at the cout<<endl. When I erase it, the program doesn't even print anything. It just prints the segfault. Aparently the program never reach to sort the vector.

#include <iostream>
#include <vector>
using namesapce std
void inserctionSort(std::vector<double> &v, int i, int j)
{
 double temp;
 for(i; i < v.size(); i++)
 {
    temp = v[i];

    j = i - 1;
    while((v[j] > temp) && (j >= 0))
    {
        v[j+1] = v[j];
        j--;
    }
    v[j+1] = temp;
 }

      }

void merge_(std::vector<double> &v, int i, int k, int j)
{
 std::vector<double> w(v.size());
 int n = j - i + 1;
 int p = i;
 int q = k + 1;

 for(int l = 0; l < n; l++)
 {
    if(p <= k && (q > j || v[p] <= v[q]))
    {
        w[l] = v[p];
        p++;
    }else
    {
        w[l] = v[q];
        q++;
    }
}

for(int l = 0; l < n; l++)
    v[i - 1 + l] = w[l];

}

void mergeSort(std::vector<double> &v, int i, int j)
{
 int n = j - i + 1, n0 = 3;
 int k;

 if(n <= n0)
 {
    inserctionSort(v,i,j);
 }else
 {
    k = i - 1 + n / 2;
    mergeSort(v, i, k);
    mergeSort(v, k + 1, j);
    merge_(v, i, k, j);
 }
}

int main()
{
vector<double> v1 = {3.2,4.1,55.42,2.24,5.424,667.32,35.54};
cout<<"Vector desordenado: ";

for(int i = 0; i < v1.size(); i++)
    cout<<v1[i]<<", ";
cout<<"hola";
cout<<endl;
cout<<"hola";
mergeSort(v1, 0, v1.size()-1); //--> Core generado
//quickSort(v1, 0, v1.size()-1);

cout<<"Vector ordenado: ";
for(int i = 0; i < v1.size(); i++)
    cout<<v1[i]<<", ";

return 0;
}

Answer 1

You have problems in your code with vector indices assuming value -1 inside a couple of loops. I have corrected these mistakes below, a working version of your code:

#include <iostream>
#include <vector>

using namespace std;

void inserctionSort(vector<double> &v, int i, int j)
{
    int v_size = v.size();
    double temp;
    for (; i < v_size; i++) {
        temp = v[i];
        j = i - 1;
        while ( (j >= 0) && (v[j] > temp) ) {  // swapped conditions, as when j=-1, v[j]>temp is undefined
            v[j+1] = v[j];
            j--;
        }
        v[j+1] = temp;
    }
}

void merge_(vector<double> &v, int i, int k, int j)
{
    vector<double> w( v.size() );
    int n = j - i + 1;
    int p = i;
    int q = k + 1;

    for (int l = 0; l < n; l++) {
        if ( p <= k && (q > j || v[p] <= v[q]) ) {
            w[l] = v[p];
            p++;
        } else {
            w[l] = v[q];
            q++;
        }
    }

    for(int l = 0; l < n; l++)      
        v[i + l] = w[l];          // deleted -1 from v[i - 1 + l], as it leads to v[-1] for i,l = 0
}

void mergeSort(vector<double> &v, int i, int j)
{
    int n = j - i + 1, n0 = 3;  // n = v.size()
    int k;

    if (n <= n0) {
        inserctionSort(v,i,j);
    } else {
        k = i - 1 + n / 2;
        mergeSort(v, i, k);
        mergeSort(v, k + 1, j);
        merge_(v, i, k, j);
    }
}

int main()
{
    vector<double> v1 = {3.2,4.1,55.42,2.24,5.424,667.32,35.54};
    cout<<"Vector desordenado: ";

    for (unsigned i = 0; i < v1.size(); i++)
        cout<<v1[i]<<", ";
    cout << "hola";
    cout << endl;
    cout << "hola";
    mergeSort(v1, 0, v1.size()-1); //--> Core generado
    //quickSort(v1, 0, v1.size()-1);

    cout<<"Vector ordenado: ";
    for (unsigned  i = 0; i < v1.size(); i++)
        cout << v1[i] << ", ";

    return 0;
}