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);
}
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?
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.
User contributions licensed under CC BY-SA 3.0