I am trying to sort a random array (size of 100) with integers 1-500 for 150,000 experiments. I also want to find the average amount of iterations for recursive and iterative quick sorts. However, I am having issues with all of those. My output and relevant code is posted below, if anyone knows why my output is so large, please point out the issue and lead me in the right direction. Once again, I'm not looking for answers, just a nudge in the right direction. I am newish to C++ and still learning, thank you for any help!
// RecursiveVsIterativeQuick.cpp
#include <iostream>
#include "RecursiveVsIterativeQuick.h"
#include "QuickSortAnalysis.h"
#include <cmath>
void RecursiveVsIterativeQuick::iterativeSort(int arr[], int n, long long& iterations)
{
std::stack<int> stack;
int low = 0;
int high = n - 1;
QuickSort quickSort; // Instantiate an object of the QuickSort class
stack.push(low);
stack.push(high);
while (!stack.empty())
{
high = stack.top();
stack.pop();
low = stack.top();
stack.pop();
// Set pivot element at its correct position in the sorted array
int pivotIndex = quickSort.partition(arr, low, high, iterations);
// If there are elements on the left side of pivot, push them to the stack
if (pivotIndex - 1 > low)
{
stack.push(low);
stack.push(pivotIndex - 1);
}
// If there are elements on the right side of pivot, push them to the stack
if (pivotIndex + 1 < high)
{
stack.push(pivotIndex + 1);
stack.push(high);
}
}
}
void RecursiveVsIterativeQuick::runExperiments(int experiments, int arraySize)
{
this->arraySize = arraySize;
this->experiments = experiments; // Assign the parameters to the class member
srand(static_cast<unsigned>(time(nullptr)));
for (int i = 0; i < experiments; ++i)
{
int* randomArray = new int[arraySize];
for (int j = 0; j < arraySize; ++j)
{
randomArray[j] = rand() % 500 + 1;
}
long long recursiveIterations;
QuickSort quickSort;
quickSort.recursiveSort(randomArray, 0, arraySize - 1, recursiveIterations);
cumulativeRecursiveIterations += recursiveIterations;
if (recursiveIterations > maxRecursiveIterations)
{
maxRecursiveIterations = recursiveIterations;
}
if (recursiveIterations < minRecursiveIterations)
{
minRecursiveIterations = recursiveIterations;
}
long long iterativeIterations;
iterativeSort(randomArray, arraySize, iterativeIterations);
cumulativeIterativeIterations += iterativeIterations;
if (iterativeIterations > maxIterativeIterations)
{
maxIterativeIterations = iterativeIterations;
}
if (iterativeIterations < minIterativeIterations)
{
minIterativeIterations = iterativeIterations;
}
delete[] randomArray; // Free the allocated memory
}
}
void RecursiveVsIterativeQuick::displayMetrics()
{
double worstCaseFormula = arraySize * arraySize;
double bestCaseFormula = arraySize * log2(arraySize);
double cumlRecursiveIterations = static_cast<double>(cumulativeRecursiveIterations) / this->experiments;
double cumlIterativeIterations = static_cast<double>(cumulativeIterativeIterations) / this->experiments;
double ratioAvgToMaxRecursive = cumlRecursiveIterations / worstCaseFormula;
double ratioAvgToMinRecursive = cumlRecursiveIterations / bestCaseFormula;
double ratioAvgToMaxIterative = cumlIterativeIterations / worstCaseFormula;
double ratioAvgToMinIterative = cumlIterativeIterations / bestCaseFormula;
std::cout << "Recursive QuickSort Cumulative # of Iterations: " << cumlRecursiveIterations << std::endl;
std::cout << "Recursive QuickSort Maximum Iterations (Worst Case): " << maxRecursiveIterations << " (Calculated: " << worstCaseFormula << ")" << std::endl;
std::cout << "Recursive QuickSort Minimum Iterations (Best Case): " << minRecursiveIterations << " (Calculated: " << bestCaseFormula << ")" << std::endl;
std::cout << "Recursive QuickSort Ratio of Avg to Max: " << ratioAvgToMaxRecursive << std::endl;
std::cout << "Recursive QuickSort Ratio of Avg to Min: " << ratioAvgToMinRecursive << std::endl;
std::cout << "\nIterative QuickSort Cumulative # of Iterations: " << cumlIterativeIterations << std::endl;
std::cout << "Iterative QuickSort Maximum Iterations (Worst Case): " << maxIterativeIterations << " (Calculated: " << worstCaseFormula << ")" << std::endl;
std::cout << "Iterative QuickSort Minimum Iterations (Best Case): " << minIterativeIterations << " (Calculated: " << bestCaseFormula << ")" << std::endl;
std::cout << "Iterative QuickSort Ratio of Avg to Max: " << ratioAvgToMaxIterative << std::endl;
std::cout << "Iterative QuickSort Ratio of Avg to Min: " << ratioAvgToMinIterative << std::endl;
}
// RecursiveVsIterativeQuick.h
#pragma once
#include <iostream>
#include <stack>
#include <climits>
class RecursiveVsIterativeQuick
{
public:
void runExperiments(int experiments, int arraySize);
void displayMetrics();
private:
void iterativeSort(int arr[], int n, long long& iterations);
int arraySize;
int experiments;
unsigned long long cumulativeRecursiveIterations = 0;
unsigned long long maxRecursiveIterations = 0;
unsigned long long minRecursiveIterations = LLONG_MAX;
unsigned long long cumulativeIterativeIterations = 0;
unsigned long long maxIterativeIterations = 0;
unsigned long long minIterativeIterations = ULLONG_MAX;
};
#include "QuickSortAnalysis.h"
#include <stack>
void QuickSort::swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
int QuickSort::partition(int arr[], int low, int high, long long& iterations)
{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++)
{
iterations++;
if (arr[j] < pivot)
{
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
void QuickSort::recursiveSort(int arr[], int low, int high, long long& iterations)
{
if (low < high)
{
int pivotIndex = partition(arr, low, high, iterations);
recursiveSort(arr, low, pivotIndex - 1, iterations);
recursiveSort(arr, pivotIndex + 1, high, iterations);
}
}
void QuickSort::iterativeSort(int arr[], int low, int high, long long& iterations)
{
// Create an auxiliary stack
std::stack<int> stack;
// Initialize top of the stack
stack.push(low);
stack.push(high);
// Continue until the stack is empty
while (!stack.empty())
{
// Pop high and low
high = stack.top();
stack.pop();
low = stack.top();
stack.pop();
// Set pivot element at its correct position in the sorted array
int pivotIndex = partition(arr, low, high, iterations);
// If there are elements on the left side of pivot, push them to the stack
if (pivotIndex - 1 > low)
{
stack.push(low);
stack.push(pivotIndex - 1);
}
// If there are elements on the right side of pivot, push them to the stack
if (pivotIndex + 1 < high)
{
stack.push(pivotIndex + 1);
stack.push(high);
}
}
}
// QuickSortAnalysis.h
#pragma once
class QuickSort
{
public:
void recursiveSort(int arr[], int low, int high, long long& iterations);
void iterativeSort(int arr[], int low, int high, long long& iterations);
int partition(int arr[], int low, int high, long long& iterations);
private:
void swap(int& a, int& b);
};
// main.cpp
#include <iostream>
#include "BubbleSortAnalysis.h"
#include "RecursiveVsIterativeBubble.h"
#include "RecursiveVsIterativeQuick.h"
int main()
{
RecursiveVsIterativeBubble bubbleComparator;
RecursiveVsIterativeQuick quickComparator;
const int experiments = 150000;
const int arraySize = 100;
bubbleComparator.runExperiments(experiments, arraySize);
bubbleComparator.displayMetrics();
quickComparator.runExperiments(experiments, arraySize);
quickComparator.displayMetrics();
return 0;
}
OUTPUT
Recursive QuickSort Cumulative # of Iterations: 4.86082e+07
Recursive QuickSort Maximum Iterations (Worst Case): 14757395259064843842 (Calculated: 10000)
Recursive QuickSort Minimum Iterations (Best Case): 9223372036854775807 (Calculated: 664.386)
Recursive QuickSort Ratio of Avg to Max: 4860.82
Recursive QuickSort Ratio of Avg to Min: 73162.6
Iterative QuickSort Cumulative # of Iterations: 3.37282e+08
Iterative QuickSort Maximum Iterations (Worst Case): 14757395259642192273 (Calculated: 10000)
Iterative QuickSort Minimum Iterations (Best Case): 14757395258967645899 (Calculated: 664.386)
Iterative QuickSort Ratio of Avg to Max: 33728.2
Iterative QuickSort Ratio of Avg to Min: 507659