0

I have got an assignment to implement quicksort(pivot is always the first element of the array while partitioning). I am getting correct output for small arrays, but the assignment has a text file containing 10,000 integers. While sorting this input, I am getting stack overflow. I tried allocating heap memory by using new, but still getting the error. How to handle this? Here is the code : 

#include<iostream>
#include<fstream>
#include<string>

using namespace std;
const int len = 10000;
int counter = 0;

void qsort(int *arr1, int start1, int end1);
int partition(int *arr2, int start2, int end2);

int main(void)
{
    int* arr = new int[len];
    int i = 0;
    fstream FILE;
    FILE.open("text.txt");
    if (FILE.is_open())
    {
        string line;
        while (getline(FILE, line))
        {
            arr[i] = stoi(line);
            i++;
        }
        FILE.close();
    }
    qsort(arr, 0, len - 1);
    for (int i = 0; i < len; i++)
        cout << arr[i];
    cout << counter;
    delete[] arr;
    return 0;
}

void qsort(int* arr, int start, int end)
{
    if (end - start == 0)
        return;
    else
    {
        counter += end - start;
        int temp = partition(arr, start, end);
        if (temp == end)
            qsort(arr, start, temp - 1);
        else if (temp == start)
            qsort(arr, temp + 1, end);
        else
        {
            qsort(arr, 0, temp - 1);
            qsort(arr, temp + 1, end);
        }
    }
}

int partition(int* arr, int start, int end)
{
    int pivot = arr[start];
    int i = start, j = start;
    for (; j <= end; j++)
    {
        if (arr[j] < pivot)
        {
            int temp = arr[i + 1];
            arr[i + 1] = arr[j];
            arr[j] = temp;
            i++;
        }
    }
    int tmp = arr[start];
    arr[start] = arr[i];
    arr[i] = tmp;
    return i;
}
Adam
  • 2,820
  • 1
  • 13
  • 33
Adarsh Mall
  • 1
  • 2
  • 1
    Avoid recursion and use an iterative algorithm or increase the stack size. – Thomas Sablik Jun 05 '20 at 08:56
  • in c and c++ (or for process in general) in linux os you can extending the stack limiters on behalf the heap segment. its your responsibilty to write a good recursion function and knowing the depth of the calls. you can add some logic to the function inorder to determine how much stack available in each call by reading `%esp`, and remember its value goes down. You already know your defaulted max size of the stack from the environment, as well as your threads' starting point. if you working with gcc, gcc has great assembly support, unlike some flakes out there. – Adam Jun 05 '20 at 08:59
  • Are you sure the recursion terminates? – G.M. Jun 05 '20 at 08:59
  • @ThomasSablik Do you know about an iterative implementation of quick sort? – Daniel Langr Jun 05 '20 at 09:06
  • @DanielLangr No – Thomas Sablik Jun 05 '20 at 09:14
  • Your stack overflow is likely caused by recursion itself, not by that array (10000 elements is a very small array). Your relatively simply implementation of quick sort is prone to worst-case data, where the recursion depth may be _O(n)_ and time complexity _O(n^2)_. There are ways how to avoid this, such as _tail-call-elimination_ and better selection of pivot (e.g., randomized, median-of-three, etc.). – Daniel Langr Jun 05 '20 at 09:14
  • 2
    There are some strange things happening in your code. You declare a dynamic array but you use a const size that you know a priori. The number of elements is `i` but you sort all `len` elements and you print them. – Thomas Sablik Jun 05 '20 at 09:17
  • @G.M. Yes, it does terminate – Adarsh Mall Jun 06 '20 at 10:08
  • @DanielLangr It is given to us to choose the first element as the pivot – Adarsh Mall Jun 06 '20 at 10:09
  • @AdarshMall Just ran your code on some test data and the recursion didn't terminate. When I interrupted it under gdb the call stack was about 20000 deep. – G.M. Jun 06 '20 at 10:37
  • Could you try this end-recursion condition: `if (end - start) <= 1`? Or, put there `assert(end >= start);`. – Daniel Langr Jun 06 '20 at 12:17

0 Answers0