am trying to work on a program that passes several arrays to a quick sort aqlgor

Question

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

{"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 to get 23 23 23 and 182 182 182 for number of memory acesses. so I am overcounting 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 merged numbers

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 to merged numbers

compareCount++;

while (leftPos <= j) {

compareCount++;

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

totalOpp+=2;

++leftPos;

++mergePos;

}

// If right partition is not empty, add remaining elements to merged 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++;

}

}

Explanation / Answer

here is your modified merge function :----------------------->>>>>>>>>>>>>>>>>

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 merged numbers
while (leftPos <= j && rightPos <= k) {   
compareCount++;
if ((*numbers)[leftPos] < (*numbers)[rightPos]) {
mergedNumbers[mergePos] = (*numbers)[leftPos];
  totalOpp+=2;
++leftPos;
}
else {
mergedNumbers[mergePos] = (*numbers)[rightPos];
  totalOpp+=2;
++rightPos;

}
++mergePos;
}

// If left partition is not empty, add remaining elements to merged numbers
while (leftPos <= j) {
compareCount++;
mergedNumbers[mergePos] = (*numbers)[leftPos];
totalOpp+=2;
++leftPos;
++mergePos;
}

// If right partition is not empty, add remaining elements to merged numbers
while (rightPos <= k) {
mergedNumbers[mergePos] = (*numbers)[rightPos];
totalOpp+=2;
++rightPos;
++mergePos;
}

// Copy merge number back to numbers
for (mergePos = 0; mergePos < mergedSize; ++mergePos) {
(*numbers)[i + mergePos] = mergedNumbers[mergePos];
totalOpp+=2;
}
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.