My issue is that I get an exception thrown when my array size becomes too big: "Unhandled exception at 0x005B3BC7 in throw away.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x01002F68)". I need to be be able to run this code with an array/vector size n = 100000, but as of right now it is only working with n = 1000. Anything past this threshold causes VS to throw a stack overflow exception. 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?
#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 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(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 = 100000; // works with n = 1000
vector<int> a(n); // originally int* a = new int[n]
vector<int> b(n); // originally int* b = new int[n]
vector<int> c(n); // originally int* c = new int[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 << "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];
}
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 << "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);
}
Stack overhead can be reduced to O(log(n)) by recursing on the smaller partition, then looping back for the larger partition. Worst case time complexity is still O(n^2).
void quickSort(std::vector<int> &arr, int left, int right) {
while(right - left > 10){
int M = left + ((right - left) / 2);
int j = partition(arr, left, right - 1, M);
if((j - left) < (right - j)){ // recurse on smaller, loop on larger
quickSort(arr, left, j);
left = j;}
} else {
quickSort(arr, j + 1, right);
right = j;
}
}
if(right - left > 0)
insertionSort(arr, left, right); // insertion sort needs a fix
}