Implement a function in c++ which takes in a vector of integers and also takes i
ID: 3776200 • Letter: I
Question
Implement a function in c++ which takes in a vector of integers and also takes in another integer d which we will refer to as depth. The function will recursively call quicksort while decrementing depth until the depth has reached 0. Thenpoithe algorithm will switch over to heapsort to finish the sorting of the vector. For this problem also comment in the code what the value of d needs to with respect to the size of the vector n for the algorithm to have worst case run time of O(n log(n)).
#include
#include
using namespace std;
void quicksort(vector & items)
{
if(items.size() > 1)
{
vector small;
vector same;
vector large;
int pivot = items[0];
for(int i = 1; i < items.size(); i++)
{
if(items[i] < pivot)
small.push_back(items[i]);
else if(items[i] > pivot)
large.push_back(items[i]);
else
same.push_back(items[i]);
}
quicksort(small);
quicksort(large);
std::move(begin(small),end(small),begin(items)); //moving the piece of memory that is small to the items memory
std::move(begin(same),end(same),begin(items) + small.size());
std::move(begin(large),end(large),end(items) - large.size());
}
else
{
//Do nothing
}
}
int leftChild(int i)
{
return 2*i + 1;
}
void percDown(vector & v, int i, int n)
{
int child;
//int leftChild;
int temp;
for(temp = v[i]; leftChild(i) < n; i = child)
{
child = leftChild(i);
if(child != n-1 && v[child] < v[child + 1]) //compare children
{
child++; //We want our right child
}
if(temp < v[child])
{
v[i] = v[child]; //Swapping
v[child] = temp;
}
else
{
break;
}
}
}
void heapsort(vector & v)
{
for(int i = v.size() /2 -1; i >= 0; --i)
{
percDown(v, i, v.size()); //Build Heap
}
for(int j = v.size() - 1; j > 0; --j)
{
swap(v[0],v[j]);
percDown(v, 0, j); //Remove max
}
}
int main()
{
int a[] = {1,10,3,2,5,8};
vector v(a,a + sizeof(a)/sizeof(int));
for(int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
cout << "Sorted " << endl;
quicksort(v);
for(int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
heapsort(v);
for(int i = 0; i < v.size(); i++)
{
cout << v[i] << endl;
}
mixSort(v)
for(int i = 0 i < v.size(); i++)
{
cout < }
int x;
cin >> x;
}
Explanation / Answer
#include
#include
using namespace std;
void quicksort(vector & items)
{
if(items.size() > 1)
{
vector small;
vector same;
vector large;
int pivot = items[0];
for(int i = 1; i < items.size(); i++)
{
if(items[i] < pivot)
small.push_back(items[i]);
else if(items[i] > pivot)
large.push_back(items[i]);
else
same.push_back(items[i]);
}
quicksort(small);
quicksort(large);
std::move(begin(small),end(small),begin(items)); //moving the piece of memory that is small to the items memory
std::move(begin(same),end(same),begin(items) + small.size());
std::move(begin(large),end(large),end(items) - large.size());
}
else
{
//Do nothing
}
}
int leftChild(int i)
{
return 2*i + 1;
}
//comment this method for your solution.....
void percDown(vector & v, int i, int n)
{
int child;
//int leftChild;
int temp;
for(temp = v[i]; leftChild(i) < n; i = child)
{
child = leftChild(i);
if(child != n-1 && v[child] < v[child + 1]) //compare children
{
child++; //We want our right child
}
if(temp < v[child])
{
v[i] = v[child]; //Swapping
v[child] = temp;
}
else
{
break;
}
}
}
void heapsort(vector & v)
{
for(int i = v.size() /2 -1; i >= 0; --i)
{
percDown(v, i, v.size()); //Build Heap
}
for(int j = v.size() - 1; j > 0; --j)
{
swap(v[0],v[j]);
percDown(v, 0, j); //Remove max
}
}
int main()
{
int a[] = {1,10,3,2,5,8};
vector v(a,a + sizeof(a)/sizeof(int));
for(int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
cout << "Sorted " << endl;
quicksort(v);
for(int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
heapsort(v);
for(int i = 0; i < v.size(); i++)
{
cout << v[i] << endl;
}
mixSort(v)
for(int i = 0 i < v.size(); i++)
{
cout < }
int x;
cin >> x;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.