Trying Work Program Passes Several Arrays Quick Sort Aqlgorithm C Count Number Comparison Q26356068

am trying to work on a program that passes several arrays to aquick sort aqlgorithm. in C++. and it will count number ofcomparisons and number of memory acesses. When I pass in thearuments :

{“Sample01″:[405671699,-1331214237,1253806977,-1731382277,1366371255,580460112,1558890951,-1776117163,-381653001,-2082221313],”Sample02″:[-1131041625,1134553371,-1329801767,2119832120,-1070564737,-1097067266,2091875263,-1800615267,1963499175,1208795062],”Sample03”:[-671509013,1183270444,-1809106133,2083837920,-533105388,373812996,1124237175,-869357156,1976027802,-375978812],

I get the numbers 146 146 146 and 99 99 99 when I am supposed toget 23 23 23 and 182 182 182 for number of memory acesses. so I amovercounting somewhere. can someone help me with this code?

// Merge Sort

#include “mergesort.h”

void MergeSort(std::vector<int>* numbers, int&compareCount, int &totalOpp) {

MergeSortRecurse(numbers, 0, numbers->size() – 1,compareCount, totalOpp);

}

void MergeSortRecurse(std::vector<int>* numbers, int i,int k, int &compareCount, int &totalOpp) {

int j = 0;

compareCount++;

if (i < k) {

j = (i + k) / 2; // Find the midpoint in the partition

// Recursively sort left and right partitions

MergeSortRecurse(numbers, i, j, compareCount, totalOpp);

MergeSortRecurse(numbers, j + 1, k, compareCount, totalOpp);

  

// Merge left and right partition in sorted order

Merge(numbers, i, j, k, compareCount, totalOpp);

}

}

void Merge(std::vector<int>* numbers, int i, int j, int k,int &compareCount, int &totalOpp) {

int mergedSize = k – i + 1; // Size of merged partition

int mergePos = 0; // Position to insert merged number

int leftPos = 0; // Position of elements in left partition

int rightPos = 0; // Position of elements in right partition

std::vector<int> mergedNumbers;

mergedNumbers.resize(mergedSize);

totalOpp++; // Dynamically allocates temporary array

// for merged numbers

leftPos = i; // Initialize left partition position

rightPos = j + 1; // Initialize right partition position

// Add smallest element from left or right partition to mergednumbers

compareCount++;

while (leftPos <= j && rightPos <= k) {

compareCount++;   

compareCount++;

if ((*numbers)[leftPos] < (*numbers)[rightPos]) {

mergedNumbers[mergePos] = (*numbers)[leftPos];

++leftPos;

}

else {

mergedNumbers[mergePos] = (*numbers)[rightPos];

++rightPos;

}

++mergePos;

}

// If left partition is not empty, add remaining elements tomerged numbers

compareCount++;

while (leftPos <= j) {

compareCount++;

mergedNumbers[mergePos] = (*numbers)[leftPos];

totalOpp+=2;

++leftPos;

++mergePos;

}

// If right partition is not empty, add remaining elements tomerged numbers

compareCount++;

while (rightPos <= k) {

compareCount++;

mergedNumbers[mergePos] = (*numbers)[rightPos];

totalOpp+=2;

++rightPos;

++mergePos;

}

// Copy merge number back to numbers

compareCount++;

for (mergePos = 0; mergePos < mergedSize; ++mergePos) {

(*numbers)[i + mergePos] = mergedNumbers[mergePos];

totalOpp+=2;

compareCount++;

}

}

0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply

Your email address will not be published. Required fields are marked *