1

We are supposed to compare the speeds of each sort with 10000 inputs. They all work by themselves but when I add them together in the program I think perhaps merge sort takes a lot of space so I always get an unhandled exception: StackOverflow once I reach quicksort. Does anyone know a solution to this problem to perhaps make it so merge sort doesn't take a lot of space (if that is the problem)? Specifically, the exception is thrown at the partition function for quicksort.

#include <iostream>
#include <fstream>
#include <ctime>
using namespace std;

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int *L = new int[n1];
    int *R = new int[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0; 
    j = 0; 
    k = l; 
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int partition(int arr[], int start, int end) { //start is 0 and end is counter-1
    int pivot = start; //remember start here
    int imp = arr[end];
    for (int i = start; i < end; i++) { //remember this is start and end;
        if (arr[i] <= imp) {
            int temp = arr[i];
            arr[i] = arr[pivot];
            arr[pivot] = temp;
            pivot++;
        }
    }
    int p = arr[pivot];
    arr[pivot] = arr[end];
    arr[end] = p;
    return pivot;
}

void quicksort(int arr[], int start, int end) {
    if (start < end) {
        int index = partition(arr, start, end);
        quicksort(arr, start, index - 1);
        quicksort(arr, index + 1, end);
    }
}

int main() {
    clock_t timereq;
    double time_taken;
    ifstream in("input3.txt");
    int size;
    in >> size;
    int num;
    int *arrq = new int[size];
    int i = 0;
    while (!in.eof()) {
        in >> num;
        arrq[i] = num;
        i++;
    }
    timereq = clock();
    mergeSort(arrq, 0,size-1);
    timereq = clock() - timereq;
    time_taken = double(timereq) / CLOCKS_PER_SEC; /// double(CLOCKS_PER_SEC);
    cout << time_taken << endl;
    
    timereq = clock();
    quicksort(arrq, 0,size-1);
    timereq = clock() - timereq;
    time_taken = double(timereq) / CLOCKS_PER_SEC; /// double(CLOCKS_PER_SEC);
    cout << time_taken << endl;

    for (i = 0; i < size; i++) {
        cout << arrq[i] << endl;
    }
}

The input looks for example like this, the number of values and then the values:

8
3 1 4 1 5 9 2 6
Improve this question
8
  • 1
    And when you used your debugger to run your program, what did you see? This is precisely what a debugger is for. If you don't know how to use a debugger this is a good opportunity to learn how to use it to run your program one line at a time, monitor all variables and their values as they change, and analyse your program's logical execution flow. Knowing how to use a debugger is a required skill for every C++ developer, no exceptions. With your debugger's help you should be able to quickly find all bugs in this and all future programs you write, without having to ask anyone for help. Commented Oct 4, 2020 at 21:11
  • You should use a std::stack and an appropriate struct for the input parameters in a loop instead of recursive calls to avoid stack overflows. The stack size is very limited. Commented Oct 4, 2020 at 21:11
  • @Sam Well, a debugger will show you that the funcrion is called many times and at some point stops. Unlikely that you will heal the problem just with this information, unless you missed to have a silly bug in the recursive calls ending condition. Commented Oct 4, 2020 at 21:14
  • 1
    @πάνταῥεῖ - any debugger worth it's salt will allow one to inspect the stack frames. I'm no exception, I've had bugs resulting in stack overflows. The debugger showed me the stack frames, the parameters of each recursive call, and based on that it was possible to identify the flaw in the recursion logic. Commented Oct 4, 2020 at 21:47
  • @Sam Same for me. But sometimes it turns out that the flaw is to use recursive function calls at all. I always prefer to use a loop and a stack, not only it's better readable and understandable, it's also more robust against such limitations like the local call stack size available. Commented Oct 4, 2020 at 21:51

2 Answers 2

Reset to default
1

You should really follow the suggestions given in the comments above, and directly tackle the root of the problem (limited stack size) by redesigning your code with stack data structures in place, so to specifically avoid memory-draining recursions.

However, you could also in principle cut corners, and adopt a dirtier and quicker solution: just add flags to your compiler to let it increase the size of the stack.

If you use gcc, you can do this by inserting the -Wl, --stack,<size> keys if compiling from the prompt. The <size> key above could be any size bigger than your current stack size, -Wl, --stack,1000000000 (9 zeros) for instance.

If you instead are using an IDE, I happen to know how to do this on Codeblocks: go to Settings->Compiler->Global Compiler Settings->Linker Settings-> add the line above under the Other Linker Options field.

See also stackoverflow: How to increase stack size when compiling a C++ program using MinGW compiler

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

The problem with quicksort is its worse case behavior:

  • if the partition function does not split the dataset in balanced halves, the complexity can reach O(N2) instead of the average O(N.log(N)).
  • in your case, the worst case occurs when the list is already sorted: The pivot splits the array into N-1 and 1 parts, causing the recursion to occur N times, probably too much for the default stack depth.
  • there is a logic error in your benchmark that causes this worst case behavior to occur every time: you measure the time for mergeSort() to sort arrq ad then you do the same for quicksort on the same array, that was just sorted by mergeSort. You should make a copy of the original array and pass that to quicksort, but you must also fix quicksort to avoid this stack overflow.

You can fix this problem by changing the quicksort function to recurse on the smaller half and iterate on the larger one:

void quicksort(int arr[], int start, int end) {
    while (start < end) {
        int index = partition(arr, start, end);
        if (index - start < end - index) {
            quicksort(arr, start, index - 1);
            start = index + 1;
        } else {
            quicksort(arr, index + 1, end);
            end = index - 1;
        }
    }
}

This should solve the stack overflow bug, but will not reduce the time complexity. You would need to change the partition function for that, for example by choosing a pivot value at random if the default choice leads to a pathological split.

Improve this answer

1 Comment

qsort's input being sorted is not just "probably one of the test cases". You can see it in their main function: They run qsort after mergesort on the same array, so unless their mergesort is broken, their qsort always gets sorted input. Cool idea to recurse only on the smaller half, I don't think I've seen that before.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.