include #include using namespace std; int leftChild(int i)

#include <iostream> #include <vector> using namespace std; int leftChild(int i)

ID: 3776283 • Letter: #

Question

#include <iostream>
#include <vector>

using namespace std;

int leftChild(int i)
{
return 2*i + 1;
}

void percDown(vector<int> & 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 left and right child
  {
   child++; //We want our right child
  }
  if(temp < v[child])
  {
   v[i] = v[child]; //Swapping the greater child
   v[child] = temp;
  }
  else
  {
   break;
  }
}
}

void heapsort(vector<int> & v)
{
for(int i = v.size() /2 -1; i >= 0; --i)
{
  percDown(v, i, v.size()); //Building the heap
}
for(int j = v.size() - 1; j > 0; --j)
{
  swap(v[0],v[j]);
  percDown(v, 0, j); //Removing the max from the heap
}

}

void quicksort(vector<int> & items)
{
if(items.size() > 1)
{
  vector<int> small;
  vector<int> same;
  vector<int> large;

  int pivot = items[0];
  for(int i = 0; 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
}
}

this is what i have now all i need to add is this two

3 Mixsort

Implement a function or method in the language of your choice which takes in a vector or list

of integers and also takes in another integer d which we will refer to as depth. The function will

recursively call quicksort similar to problem 2 while decrementing depth until the depth has

reached 0. At which point the algorithm will switch over to the heapsort you implemented in

problem 1 to nish 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)).

4 Program

You should have the above 3 problems implemented as functions. You also should have an

implementation of a heap included in your code. Make a basic main function that does a test

run for each of the 3 functions above.

Explanation / Answer

PROGRAM CODE:

#include <iostream>
#include <vector>
using namespace std;

int leftChild(int i)
{
return 2*i + 1;
}
void percDown(vector<int> & 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 left and right child
{
child++; //We want our right child
}
if(temp < v[child])
{
v[i] = v[child]; //Swapping the greater child
v[child] = temp;
}
else
{
break;
}
}
}
void heapsort(vector<int> & v)
{
for(int i = v.size() /2 -1; i >= 0; --i)
{
percDown(v, i, v.size()); //Building the heap
}
for(int j = v.size() - 1; j > 0; --j)
{
swap(v[0],v[j]);
percDown(v, 0, j); //Removing the max from the heap
}
}

void quicksort(vector<int> & items)
{
if(items.size() > 1)
{
vector<int> small;
vector<int> same;
vector<int> large;
int pivot = items[0];
for(int i = 0; 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
}
}

void mixsort(vector<int> & items, int d)
{
   while(d>0)
   {
       quicksort(items);
       d--;
   }
   heapsort(items);
}

//i worte a print function just to check the output. You can comment this anytime
void print(vector<int> & items)
{
   for(std::vector<int>::const_iterator i=items.begin(); i !=items.end(); i++)
   {
       cout<<*i<<" ";
   }
   cout<<endl;
}
//main function to initialize vectr and call the sort functions
int main()
{
   vector<int> v1 = {1,6,2,5};
   heapsort(v1);
   print(v1);
   vector<int> v2 = {3,6,1,9};
   quicksort(v2);
   print(v2);
   vector<int> v3 = {7,1,6,4};
   //best case
   mixsort(v3,0);
   //worst case
   //mixsort(v3,4);
   print(v3);
   return 0;
}

OUTPUT:

Navigate

#include <iostream> #include <vector> using namespace std; class Shape { public:

#include <iostream> #include <vector> using namespace std; int main(){ vector<st

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

#include <iostream> #include <vector> using namespace std; int leftChild(int i)

Question

Explanation / Answer

Related Questions

Navigate