quick sort c++ code error segmentation fault 11?

Question

Code:


#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
void partition(int *A, int start, int end){ //end is the position of the last number
    cout<<"start is "<<start<<" end is "<<end<<endl;
    if(end - start+1 > 1){
        int i = start + 1, j = start + 1, pivot = A[start];
        while(j <= end){
            if(A[j] <= pivot){
                swap(A[j], A[i]);
                i++;
            }
            j++;
        }
        swap(A[start], A[i-1]);
        partition(A, start, i-1);
        partition(A, i, end);
    }
    
}

void QuickSort(int *A, int n){
    partition(A, 0, n-1);
}


int main() {
    int n, method;
    string sortMethod[ ] = {
            "Insertion sort", "Selection sort", "Bubble sort", "Merge sort", "Quick sort"
    };
    int m = sizeof(sortMethod)/sizeof(string);
    srand(time(0));
    
    while (true){
        cout << "Number of test marks: ";
        cin >> n;
        if ( n==0 ) break;
        int *A = new int[n];
        for (int i=0; i < n; i++) cin>>A[i];
        //A[i] = rand()%101;

        for (int i=0; i < n; i++)cout << A[i] << " ";
        cout<<endl<<endl;


        cout << "Sorting method: \n"; 
        for (int i=0; i < m; i++) cout << i+1 << ": " << sortMethod[i] << endl;
        // cin >> method;
        method = 5;
        cout<<endl;
        int t = time(0);
        
        QuickSort(A,n);

        if (method > m) continue;       
        cout << sortMethod[method-1] << endl;
        if (n <= 100) {
            for (int i=0; i < n; i++) {
                if (i> 0 && i%10==0) cout << endl;
                cout << A[i] << " ";
            }
            cout << endl;
        }
        else {
            cout << "Sorting completed in " <<  time(0) - t  << " sec.\n";
        }
        cout << endl;
    } 
    cout << "Program ends here."<<endl;
    return 0;
}

When some of my input numbers have the same value, I get a "Segmentation fault: 11".

For example, an input of "4 7 7 3 1" would produce infinite lines of the following output: "start is 1 end is 3".

May I ask how should I improve my code? I know that Segfault 11 happens when you try to access an invalid memory, and i think that's likely what I did here, although i cant seem to identify the error. Thanks!

Have you tried running your code through a debugger step by step? My experience is, that in that case one often finds the reason for these kinds of bugs. — Eike, Jul 06 '21 at 13:04
`-fsanitize=addr` is great at finding the cause of such problems — ikegami, Jul 06 '21 at 13:05
For testing and to ease the debugging of things like crashes, please learn the concept of *[mcve]*. Remove all your code except the bare minimum to replicate the crash, and use hard-coded values instead of user input. — Some programmer dude, Jul 06 '21 at 13:06
Another tool that is useful in such cases is a memory debugger such as valgrind. — Fred Larson, Jul 06 '21 at 13:07
`int *A = new int[n];` -- You never called `delete[]` on this. Use `std::vector A(n);` instead of this. Not only do you not have to manage the memory, you can use `at()` to check whether the index you give the vector is out-of-bounds, and will thus throw an `std::out_of_range` exception instead of a random segfault. Don't be surprised if this is the error you're getting. — PaulMcKenzie, Jul 06 '21 at 13:12
and to avoid such issues in the first place, using `std::vector` instead of manually managed arrays can help a lot — 463035818_is_not_an_ai, Jul 06 '21 at 13:12
I didn't think this through thoroughly, but from quick inspection I think it's probably `while(j <= end)`. You shouldn't be accessing `A[end]` as the last element is `A[end-1]`. You can replace `while(j<=end)` with `while(j!=end)`. You can also do `while(j — SMeznaric, Jul 06 '21 at 13:15
As a suggestion: try to use half-open ranges. This will rid you of most, if not all, the +1 and -1 in your code. https://stackoverflow.com/questions/13066884 — Jeffrey, Jul 06 '21 at 13:15
And a couple of generic tips for testing: Test the extremes! For example pass a null pointer, pass `n == 0`, pass an array of only a single element, pass an array of only two elements, three elements, pass with `n < 0`, pass an array of only negative values, an array of only zeros, an array of all the same values, an array that is already sorted, an array sorted in reverse. And any other possible corner or extreme case you could think about. — Some programmer dude, Jul 06 '21 at 13:16
@SMeznaric OP is using `end` to refer to the index of the last element, it is not the index of one past the last element. — 463035818_is_not_an_ai, Jul 06 '21 at 13:45

score 1 · Accepted Answer · answered Jul 06 '21 at 15:11

So this is what's happening here. Imagine that in a certain partition the first element (the pivot) is also the largest.

This means that in every iteration of the while loop the value of A[j]<=pivot will be true and i will be increased.

Since both i and j are increased by 1 in every iteration there value is the same, so at the end of the loop they are both equal to end+1.

Then you are invoking partition(A, start, i-1) which is really the same as partition(A, start, end) - meaning you have an infinite recursion which continues until you reach... well, stack overflow and the program crush with segfault.

The minimal fix will be to make sure that the sub partitions are strictly smaller than the original one by excluding the pivot from them. So something like this:

        partition(A, start, i-2); // i-1 is the pivot, so we don't need to include it
        partition(A, i, end);

quick sort c++ code error segmentation fault 11?

1 Answers1