Quicksort algorithm printing a segmentation fault, not working properly

Question

I am currently working on a quicksort algorithm that takes in random doubles, ints, char, and floats. Currently testing the doubles and I am getting (process 27368) exited with code -1073740791. I do know this is a segment fault, but I am not seeing an issue with what I have. The code is in C++. Here it is:

// Code for generating random doubles
vector<double> generateDouble(int size, double min, double max)
{
    srand(time(0));
    vector<double> array(size);

    for (int index = 0; index < size; ++index)
    {
        double r = (((double)rand() / (double)RAND_MAX) * (max - min)) + min;
        array[index] = r;
    }

    return array;
}

// here is the getIter() function
int Sorting::getIter() const
{
    return iter;
}

void Sorting::quickSort()
{
    int first = 0;
    int last = listData.size() - 1;
    quickSort(listData, first, last);
}

void Sorting::quickSort(vector<double>& list, int first, int last)
{
    if (first < last)
    {
        int index = partition(list, first, last);

        quickSort(list, first, index - 1);
        quickSort(list, index + 1, last); // Corrected index
    }
}

int Sorting::partition(vector<double>& list, int first, int last)
{
    double pivot = list[last - 1];
    int i = first - 1; // Initialize i with first instead of (first - 1)

    for (int j = first; j < last; j++)
    {
        if (list[j] < pivot)
        {
            // Increment i before swapping
            i++;
            swap(list[i], list[j]);
        }
        iter++;
    }
    // Swap pivot with the element at (i + 1)
    swap(list[i], list[last - 1]);
    return i;
}

// how I am calling it in main

Sorting quickDSort(dd);
time.startTimer();
quickDSort.quickSort();
time.stopTimer();
cout << "(quick sort) Double Iterations: " << quickDSort.getIter() << endl;
cout << time.getSeconds() << endl;

I have been stuck for a while, not sure what too do. Thanks.

I need the code to take the vector<double> and sort it. With that I have currently, it does not print the amount of times it takes to sort the numbers.

Answer 1

It is strange to see comments in your code that do not relate to what you actually do.

For instance,

    // Swap pivot with the element at (i + 1)
    swap(list[i], list[last - 1]);

...You're not swapping with the element at (i + 1), and actually you should.

Secondly, the last element in current subarray is not at last-1, but at last. So also that index is wrong, both in the code quoted above, as at the start of the partition function.

Here is your partition function with those bugs corrected:

int partition(vector<double>& list, int first, int last)
{
    double pivot = list[last]; // Should be last, not last-1
    int i = first - 1;

    for (int j = first; j < last; j++)
    {
        if (list[j] < pivot)
        {
            i++;
            swap(list[i], list[j]);
        }
    }
    i++; // Must increment
    swap(list[i], list[last]); // Should be last, not last-1
    return i;
}