I am trying to work on a program that passes several arrays to a quick sort aqlg
ID: 3879049 • Letter: I
Question
I am trying to work on a program that passes several arrays to a quick sort aqlgorithm. in C++. 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 92 87 76 when I am supposed to get 53 51 44. so I am overcounting somewhere. can someone help me with this code?
void QuickSort(std::vector<int>* numbers,int &compareCount, int &totalOpp) {
QuickSortRecurse(numbers, 0, numbers->size() - 1,compareCount,totalOpp);
}
void QuickSortRecurse(std::vector<int>* numbers, int i, int k, int &compareCount, int &totalOpp) {
int j = 0;
/* Base case: If there are 1 or zero elements to sort,
partition is already sorted */
compareCount++;
if (i >= k) {
return;
}
/* Partition the data within the array. Value j returned
from partitioning is location of last element in low partition. */
j = Partition(numbers, i, k,compareCount,totalOpp);
/* Recursively sort low partition (i to j) and
high partition (j + 1 to k) */
QuickSortRecurse(numbers, i, j,compareCount,totalOpp);
QuickSortRecurse(numbers, j + 1, k,compareCount,totalOpp);
return;
}
int Partition(std::vector<int>* numbers, int i, int k, int &compareCount, int &totalOpp) {
int l = 0;
int h = 0;
int midpoint = 0;
int pivot = 0;
int temp = 0;
bool done = false;
/* Pick middle element as pivot */
midpoint = i + (k - i) / 2;
pivot = (*numbers)[midpoint];
l = i;
h = k;
while (!done) {
/* Increment l while numbers[l] < pivot */
compareCount++;
while ((*numbers)[l] < pivot) {
compareCount++;
++l;
}
/* Decrement h while pivot < numbers[h] */
compareCount++;
while (pivot < (*numbers)[h]) {
--h;
compareCount++;
}
/* If there are zero or one elements remaining,
all numbers are partitioned. Return h */
compareCount++;
if (l >= h) {
done = true;
}
else {
/* Swap numbers[l] and numbers[h],
update l and h */
temp = (*numbers)[l];
(*numbers)[l] = (*numbers)[h];
(*numbers)[h] = temp;
++l;
--h;
}
}
return h;
}
Explanation / Answer
#include<iostream>
#include<vector>
using namespace std;
int Partition(std::vector<int>* numbers, int i, int k, int &compareCount, int &totalOpp) {
int l = 0;
int h = 0;
int midpoint = 0;
int pivot = 0;
int temp = 0;
bool done = false;
/* Pick middle element as pivot */
midpoint = i + (k - i) / 2;
pivot = (*numbers)[midpoint];
l = i;
h = k;
while (!done) {
/* Increment l while numbers[l] < pivot */
while ((*numbers)[l] < pivot) {
compareCount++;
++l;
}
/* Decrement h while pivot < numbers[h] */
while (pivot < (*numbers)[h]) {
--h;
compareCount++;
}
/* If there are zero or one elements remaining,
all numbers are partitioned. Return h */
compareCount++;
if (l >= h) {
done = true;
//compareCount++;
}
else {
/* Swap numbers[l] and numbers[h],
update l and h */
temp = (*numbers)[l];
(*numbers)[l] = (*numbers)[h];
(*numbers)[h] = temp;
++l;
--h;
}
}
return h;
}
void QuickSortRecurse(std::vector<int>* numbers, int i, int k, int &compareCount, int &totalOpp) {
int j = 0;
/* Base case: If there are 1 or zero elements to sort,
partition is already sorted */
compareCount++;
if (i >= k) {
return;
}
/* Partition the data within the array. Value j returned
from partitioning is location of last element in low partition. */
j = Partition(numbers, i, k,compareCount,totalOpp);
/* Recursively sort low partition (i to j) and
high partition (j + 1 to k) */
QuickSortRecurse(numbers, i, j,compareCount,totalOpp);
QuickSortRecurse(numbers, j + 1, k,compareCount,totalOpp);
return;
}
void QuickSort(std::vector<int>* numbers,int &compareCount, int &totalOpp) {
compareCount++;
QuickSortRecurse(numbers, 0, numbers->size() - 1,compareCount,totalOpp);
}
int main()
{
vector<int>*s1,s2,s3;
s1 = new vector<int>[10];
s1->push_back(405671699);
s1->push_back(-1331214237);
s1->push_back(1253806977);
s1->push_back(-1731382277);
s1->push_back(1366371255);
s1->push_back(580460112);
s1->push_back(1558890951);
s1->push_back(-1776117163);
s1->push_back(-381653001);
s1->push_back(-2082221313);
int c=0,p=1;//for initial accessing
QuickSort(s1,c,p);
cout<<" "<<c<<" "<<endl;
}
output:
53
Process exited normally.
Press any key to continue . . .
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.