Quick Sort algorithm getthing an exception thrown (partially solved)

-1

My issue is that I get an exception thrown when my array size becomes too big: "Unhandled exception at 0x00F22A67 in lab.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x00682F60)." It was recommended that I use vectors instead of arrays, but this did not solve the issue. I added a break and began to debug. That is where I noticed that this occurs when the quickSort function is entered. I'm assuming that, with such a large array/vector size, the stack becomes full as it is partitioned and divided into subarrays. What would be a recommended fix for this?

// Insertion Sort
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int j, temp = arr[i]; // make a copy of a[i]
        for (j = i - 1; j >= 0; j--) { // starting "moving left"
            if (arr[j] > temp)
                arr[j + 1] = arr[j]; // inversion detected, move a[j] to the right
            else
                break; // index j is one spot to the left of where temp belong
        }
        arr[j + 1] = temp;
    }
}

// Partition
int partition(int arr[], int left, int right, int pivotIndex) {
    int pivotValue = arr[pivotIndex];
    swap(arr[pivotIndex], arr[right]); // move pivotValue to end

    // partition the array. upon finding an element smaller than pivot,
    // swap it ot the next position in the "store"
    int store = left;
    for (int i = left; i < right; i++) {
        if (arr[i] <= pivotValue) {
            swap(arr[store], arr[i]);
            store++;
        }
    }

    swap(arr[right], arr[store]); // swap pivot to its final position
    return store;
}

// Quick Sort
// std::vector<int> &data, int left, int right
void quickSort(int arr[], int left, int right) {
    // Perform IS when sub array(s) are less than 10
    if ((right - left) < 10) {
        insertionSort(arr, right);
    }
    else {
        int M = (right - left) / 2;
        int j = partition(arr, left, right-1, M);
            quickSort(arr, left, j);    // sort the left of M
            quickSort(arr, j+1, right); // sort the right of M
    }
}

// Check if array has been ordered
bool isOrdered(int arr[], int n) {
    // array with 1 or no elements will always be sorted
    if (n <= 1)
        return true;

    for (int i = 1; i < n; i++) {
        if (arr[i-1] > arr[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    int input;

    // Prompt user with catch if input not within bounds
    do
    {
        cout << "----------------------------------------------------------------" << endl;
        cout << " Press 1 to exit the program " << endl;
        cout << " Press 2 to select the array that is sorted in increasing order " << endl;
        cout << " Press 3 to select the array that is randomly sorted " << endl;
        cout << " Press 4 to select the array that is sorted in decreasing order " << endl;
        cout << "----------------------------------------------------------------" << endl;
        cin >> input;
    } while (input != 1 && input != 2 && input != 3 && input != 4);

    while (input != 1)
    {
        int n = 10000;

        int* a = new int[n];
        int* b = new int[n];
        int* c = new int[n];

        int* a_c1 = new int[n];
        int* b_c1 = new int[n];
        int* c_c1 = new int[n];

        int* a_c2 = new int[n];
        int* b_c2 = new int[n];
        int* c_c2 = new int[n];

        if (input == 2) {
            // Fill array with numbers in ascending order
            for (int i = 0; i < n; i++) {
                a[i] = i + 1;
            }

            // create first duplicate array
            for (int i = 0; i < n; i++) {
                a_c1[i] = a[i];
            }

            // get start time for IS
            auto start = std::chrono::steady_clock::now();
            insertionSort(a_c1, n);
            // get end time
            auto end = std::chrono::steady_clock::now();
            double elapsed_time_ns = double(std::chrono::duration_cast <std::chrono::nanoseconds> (end - start).count());
            double elapsed_time_ms = double(std::chrono::duration_cast <std::chrono::milliseconds> (end - start).count());
            // output time to screen
            cout << "Elapsed time of Insertion Sort function: " << elapsed_time_ns << " ns or " << elapsed_time_ms << " ms" << endl;

            // create second duplicate array
            for (int i = 0; i < n; i++) {
                a_c2[i] = a[i];
            }

            // get start time for QS
            auto start2 = std::chrono::steady_clock::now();
            quickSort(a_c2, 0, n);
            // get end time
            auto end2 = std::chrono::steady_clock::now();
            double elapsed_time2_ns = double(std::chrono::duration_cast <std::chrono::nanoseconds> (end2 - start2).count());
            double elapsed_time2_ms = double(std::chrono::duration_cast <std::chrono::milliseconds> (end2 - start2).count());
            // output time to screen
            cout << "Elapsed time of Quick Sort function: " << elapsed_time2_ns << " ns or " << elapsed_time2_ms << " ms" << endl;

            cout << "After passing array through Insertion Sort funtion, is it sorted? " << isOrdered(a_c1, n) << endl;
            cout << "After passing array through Quick Sort funtion, is it sorted?     " << isOrdered(a_c2, n) << endl;
            
        }

        else if (input == 3) {
            // seed the PRNG (MT19937) using a variable value (in our case, rd)
            std::random_device rd;
            std::mt19937 generator(rd()); // seed by variable input
            std::uniform_int_distribution<int> distribution(1, n); // random numbers need to be in range between 1, n 
            
            for (int i = 0; i < n; i++) {
                b[i] = distribution(generator);
            }

            // create first duplicate array
            for (int i = 0; i < n; i++) {
                b_c1[i] = b[i];
            }
            
            // get start time for IS
            auto start = std::chrono::steady_clock::now();
            insertionSort(b_c1, n);
            // get end time
            auto end = std::chrono::steady_clock::now();
            double elapsed_time_ns = double(std::chrono::duration_cast <std::chrono::nanoseconds> (end - start).count());
            double elapsed_time_ms = double(std::chrono::duration_cast <std::chrono::milliseconds> (end - start).count());
            // output time to screen
            cout << "Elapsed time of Insertion Sort function: " << elapsed_time_ns << " ns or " << elapsed_time_ms << " ms" << endl;

            // create second duplicate array
            for (int i = 0; i < n; i++) {
                b_c2[i] = b[i];
            }

            // get start time for QS
            auto start2 = std::chrono::steady_clock::now();
            quickSort(b_c2, 0, n);
            // get end time
            auto end2 = std::chrono::steady_clock::now();
            double elapsed_time2_ns = double(std::chrono::duration_cast <std::chrono::nanoseconds> (end2 - start2).count());
            double elapsed_time2_ms = double(std::chrono::duration_cast <std::chrono::milliseconds> (end2 - start2).count());
            // output time to screen
            cout << "Elapsed time of Quick Sort function: " << elapsed_time2_ns << " ns or " << elapsed_time2_ms << " ms" << endl;


            cout << "After passing array through Insertion Sort funtion, is it sorted? " << isOrdered(b_c1, n) << endl;
            cout << "After passing array through Quick Sort funtion, is it sorted?     " << isOrdered(b_c2, n) << endl;
        }

        else {
            int temp_1 = n;
            for (int i = 0; i < n; i++) {
                c[i] = temp_1;
                temp_1--;
            }
            
            // create first duplicate array
            for (int i = 0; i < n; i++) {
                c_c1[i] = c[i];
            }

            // get start time for IS
            auto start = std::chrono::steady_clock::now();
            insertionSort(c_c1, n);
            // get end time
            auto end = std::chrono::steady_clock::now();
            double elapsed_time_ns = double(std::chrono::duration_cast <std::chrono::nanoseconds> (end - start).count());
            double elapsed_time_ms = double(std::chrono::duration_cast <std::chrono::milliseconds> (end - start).count());
            // output time to screen
            cout << "Elapsed time of Insertion Sort function: " << elapsed_time_ns << " ns or " << elapsed_time_ms << " ms" << endl;

            // create second duplicate array
            for (int i = 0; i < n; i++) {
                c_c2[i] = c[i];
            }

            // get start time for QS
            auto start2 = std::chrono::steady_clock::now();
            quickSort(c_c2, 0, n);
            // get end time
            auto end2 = std::chrono::steady_clock::now();
            double elapsed_time2_ns = double(std::chrono::duration_cast <std::chrono::nanoseconds> (end2 - start2).count());
            double elapsed_time2_ms = double(std::chrono::duration_cast <std::chrono::milliseconds> (end2 - start2).count());
            // output time to screen
            cout << "Elapsed time of Quick Sort function: " << elapsed_time2_ns << " ns or " << elapsed_time2_ms << " ms" << endl;

            cout << "After passing array through Insertion Sort funtion, is it sorted? " << isOrdered(c_c1, n) << endl;
            cout << "After passing array through Quick Sort funtion, is it sorted?     " << isOrdered(c_c2, n) << endl;
        }

        // Prompt user again with catch if input not within bounds
        do
        {
            cout << "----------------------------------------------------------------" << endl;
            cout << " Press 1 to exit the program " << endl;
            cout << " Press 2 to select the array that is sorted in increasing order " << endl;
            cout << " Press 3 to select the array that is randomly sorted " << endl;
            cout << " Press 4 to select the array that is sorted in decreasing order " << endl;
            cout << "----------------------------------------------------------------" << endl;
            cin >> input;
        } while (input != 1 && input != 2 && input != 3 && input != 4);
    }
    
    exit(0);
}
c++
arrays
sorting
quicksort
sizeof
asked on Stack Overflow Jul 20, 2020 by Fabian • edited Jul 21, 2020 by Fabian

2 Answers

1

In the quickSort() function, the 2 recursive calls, I do not see the start index.

What is the range of the array being used for sorting?

First recursive call goes from 0 -> j Second recursive call goes from 0 -> n-j

Isn't that obviously wrong?

answered on Stack Overflow Jul 20, 2020 by user3389943
1
swap(arr[right], arr[store]);

You're swapping with an index that is out of bounds. Every time you do that the right bound is increased by one. The exception is due to infinite recursion because of this. Making it right - 1 will do the the job in the partition function.

int j = partition(arr, 0, n, M);

Mention proper bounds. Quick sort is divide and conquer approach. Specifying 0 and n as the bounds every time makes it a whole array without the partition from the previous recursion.

answered on Stack Overflow Jul 20, 2020 by Sujan Veena • edited Jul 20, 2020 by Sujan Veena

User contributions licensed under CC BY-SA 3.0