Large value and calculation issues for quick sort algorithim in c++

47 Views Asked by At

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
0

There are 0 best solutions below