Use .cpp file below to write c++ code. Change split() function to use the midian of three methods. Show the status of the list F= [ 18, 5, 1, 3, 9, 7, 2, 12, 99, 6, 21] at the end of each phase of recursive Quick sort using median of three rule to determine the pivot key. Then write a non recursive version of this whole program using the median of three rule.
Use .cpp file below to write c++ code. Change split() function to use the midian of three methods. Show the status of the list F= [ 18, 5, 1, 3, 9, 7, 2, 12, 99, 6, 21] at the end of each phase of recursive Quick sort using median of three rule to determine the pivot key. Then write a non recursive version of this whole program using the median of three rule.
#include <iostream>
using namespace std;
static const int numValues = 11;
static int values[numValues] = { 18, 5, 1, 3, 9, 7, 2, 12, 99, 6, 21 };
void display();
void swap(int& item1, int& item2)
{
int temp = item1;
item1 = item2;
item2 = temp;
}
int split(int first, int last)
{
int splitVal = values[first];
int saveF = first;
bool onCorrectSide;
first++;
do
{
onCorrectSide = true;
while (onCorrectSide)
{
if (values[first] > splitVal)
onCorrectSide = false;
else
{
first++;
onCorrectSide = (first <= last);
}
}
onCorrectSide = (first <= last);
while (onCorrectSide)
{
if (values[last] <= splitVal)
onCorrectSide = false;
else
{
last--;
onCorrectSide = (first <= last);
}
}
if (first < last)
{
swap(values[first], values[last]);
first++;
last--;
}
} while (first <= last);
swap(values[saveF], values[last]);
display();
return last;
}
void quickSort(int first, int last)
{
if (first < last)
{
int splitPoint;
splitPoint = split(first, last);
//values[first].......values[splitPoint-1] <= splitVal
//Values[splitPoint] = splitValue
//values[splitPoint+1].......values[last] > splitVal
quickSort(first, splitPoint - 1);
quickSort(splitPoint + 1, last);
}
}
int main()
{
cout << "......................" << endl;
cout << "Array Before Sorting" << endl;
display();
cout << "......................" << endl;
quickSort(0, 10);
cout << "......................" << endl;
cout << "Array After Sorting" << endl;
display();
cout << "......................" << endl;
return 0;
}
void display()
{
for (int i = 0; i < numValues; i++)
cout << values[i] << " ";
cout << endl;
}
Step by step
Solved in 2 steps with 1 images
