Using C++, do a partial quicksort using recursion and the function: void partial
ID: 3828542 • Letter: U
Question
Using C++, do a partial quicksort using recursion and the function:
void partialsort(Vector<int> &a, int k) . . .
as k represents the top of the vector that needs to be sorted. Example:
[3, 6, 2, 10, 5, 8, 8, 1] with k=4 will result in partialsort to give [3, 2, 5, 1, 6 ,8, 8, 10] (this is only an example not exact swap). We do not care about sorting the other end of the vector list, only the bottom half of whatever k is. The partition and quicksort is below:
void partition( vector<int> &a, int first, int last, int &pivotIndex ){
choosePivot( a, first, last );
Comparable pivot = a[first];
int lastS1 = first;
int firstUnknown = first + 1;
for ( ; firstUnknown <= last; ++firstUnknown ) {
if ( a[firstUnknown] < pivot ) {
++lastS1;
objectSwap( a[firstUnknown], a[lastS1] );
}
}
// decide a new pivot
objectSwap( a[first], a[lastS1] );
pivotIndex = lastS1;
}
void quicksort( vector<int> &a, int first, int last, int k) {
int pivotIndex;
if ( first < last ) {
partition( a, first, last , pivotIndex);
quicksort( a, first, pivotIndex - 1, k);
quicksort( a, pivotIndex + 1, last, k );
}
}
void partialsort( vector<int> &a, int k ) {
quicksort( a, 0, a.size( ) - 1, k);
}
Only need to modify void quicksort( vector<int> &a, int first, int last, int k) and or partialsort.
Explanation / Answer
only modified queick sort .
No need of partialsort function
quicksort(vector <int> &a , int first, int last, int k)
{
//int pivotIndex;
if(first==last)
return a[first];
else {
int k;
k=partition(aa,first,last);
quicksort(a,first,k-1);
quicksort(a,k+1,last);
return a;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.