Quick Sort: Getting an exception thrown

[F95]

I was provided with some pseudo code to write a quick sort algorithm, but what I have so far is causing an exception to be thrown when I try to run the code. The first 'for-loop' in main outputs, then the terminal stops and throws: "Unhandled exception at 0x00542D07 in Lab.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x00A02FA8)."

// Insertion Sort (this is correct according to the pseudo code provided and requires no change)
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;
    }
}

// To find the pivot, we must find the "middle" of the index and return it
// will be used by partition function to find median of 3
int findPivot(int arr[], int n) {
    int M_i = (int)floor((n - 1) / 2);

    return M_i;
}

// Partition (this is also correct according to the pseudo code provided and requires no change - Tony Hoare alg)
int partition(int arr[], int left, int right, int pivotIndex) {
    int pivotValue = arr[pivotIndex];
    swap(arr[pivotIndex], arr[right-1]); // move pivotValue to end

    // partition the array. upon finding an element smaller than pivot,
    // swap it to 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-1], arr[store]); // swap pivot to its final position
    return store;
}

// Quick Sort (pseudo code provided, but I'm assuming my errors are here)
void quickSort(int arr[], int n) {
    // once the array has been partitioned to 10 or fewer elements
    // we perform an insertion sort on that array
    if (sizeof(arr) < 10) {
        insertionSort(arr, 10);
    }

    int M = findPivot(arr, n); // returns pivot
    int j = partition(arr, 0, n, M); // returns an index 
    quickSort(arr, j); // further partition what is to the "left of M"
    quickSort(arr, n-j); // further partition what is to the "right of M"
}

int main() {
    int input;

    int test[20] = {5, 8, 7, 10, 6, 9, 25, 8, 7, 6, 77, 99, 4, 21, 13, 61, 10, 6, 9, 25};

    cout << "Before quick sort: ";
    for (int i = 0; i < 20; i++) {
        cout << test[i] << ' ';
    }
    cout << endl;

    quickSort(test, 20);

    cout << "After quick sort: ";
    for (int i = 0; i < 20; i++) {
        cout << test[i] << ' ';
    }
    cout << endl;

exit(0);
}

[Ganado]

    if (sizeof(arr) < 10) {
        insertionSort(arr, 10);
    }

First, an array degrades into a pointer when passed to a function. You are taking the sizeof a pointer, not the array. Use n instead.

Second, Stack overflow usually means you keep calling your function recursively over and over again, eventually overflowing the stack. Like an infinite loop.

In quickSort, you are recursively calling quickSort, but you have no way to stop recursively calling quickSort, so it will just keep calling quickSort.

Perhaps you meant do to something like:

if (n < 10)
    // do insertion sort
else
    // do quick sort on each partition 

You also probably want to specify a low index and a high index, not just n. For example, when sorting the right-hand side partition, you don't want to be starting from index 0.

[F95]

Thanks, with the modification I was able to get it to run (although I kept it as sizeof(arr) < 10 because using sizeof(n) made no difference in regards to the next issue). The output to the terminal is:

Before quick sort: 5 8 7 10 6 9 25 8 7 6 77 99 4 21 13 61 10 6 9 25
After quick sort : 5 6 6 7 7 8 8 9 10 25 77 99 4 21 13 61 10 6 9 25

So it appears to be working for the sort on the left side but not the right. I added a break statement and stepped through the code, and, based on the code below, it executes the if statement (lines 2-4), and returns to main. I did an output of the sizeof(arr) and sizeof(n) and both were equal to 4.

// intitial        array         0          20
void quickSort(int arr[], int left, int right) {
    if (sizeof(arr) < 10) {
        insertionSort(arr, 10);
    }
    else {
        int M = findPivot(arr, right);
        int j = partition(arr, left, right, M);
        if (left < j) {
            quickSort(arr, left, j); // left
        }
        if (j < right) {
            quickSort(arr, j, right); // right
        }
    }
}

[Ganado]

using sizeof(n)

...No. Please stop using sizeof if you don't understand what it does. sizeof only looks at the size in bytes of the type of something, e.g. int or int*. It has nothing to do with the actual value of n.

sizeof(arr) is doing sizeof(int*), which is (most likely) either 4 or 8, depending on if you are compiling 32-bit or 64-bit, respectively.

So in your case, you're evaluating, at most, if (8 < 10), which will always be true.

In other words: You are ALWAYS entering your insertionSort branch, and never your quicksort branch!

After quick sort: 5 6 6 7 7 8 8 9 10 25 77 99 4 21 13 61 10 6 9 25

Notice how only the first 10 elements change in your output.

The issue with your quickSort is what I mentioned earlier: You need a low index and a high index to work with, not just an overall number n.

PS: Another issue to think about: What if the array has less than 10 elements? What happens in insertionSort(arr, 10)?

[F95]

Thank you, I was able to figure out the issue:

#include <iostream>
#include <chrono>
#include <cmath>
#include <math.h>
#include <random>
#include <vector>
using namespace std;

// Insertion Sort
void insertionSort(std::vector<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(std::vector<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 t0 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(std::vector<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(std::vector<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 = 1000;

        vector<int> a(n);
        vector<int> b(n);
        vector<int> c(n);

        vector<int> a_c1(n);
        vector<int> b_c1(n);
        vector<int> c_c1(n);

        vector<int> a_c2(n);
        vector<int> b_c2(n);
        vector<int> c_c2(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];
            }

            insertionSort(b_c1, n);

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

            cout << isOrdered(b_c1, n) << endl;
            cout << 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];
            }
            insertionSort(c_c1, n);

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

            cout << isOrdered(c_c1, n) << endl;
            cout << 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);
}