[Solved]C Difficulty Quicksort Function Code Run Quicksort Function Code M Trouble Bold Driverpro Q37069219
C++. Difficulty with quickSort function.
Code will not run quickSort function. The code I’m havingtrouble with is in bold.
————————————————————————————————-driverProgram.cpp
#include
#include
#include
#include
#include “quickSort.cpp”
using namespace std;
int main()
{
const int MIN_SIZE = 4;
//Array size
const int SIZE = 25;
int theArray[SIZE] = {11, 22, 33, 44, 55, 66, 77, 88, 99, 12,13,
14, 15, 16, 17, 18, 19, 18, 19, 20, 21, 22, 23, 24, 25};
cout << “List of 25 items: “;
int length = (sizeof(theArray)/sizeof(theArray[0]));
int first = 0;
int last = length – 1;
//Display array of unsorted items
for(int count = 0; count < length; count++)
{
cout << theArray[count] << ” “;
}
cout << “Sort list of 25 items: ” << endl;
//Call quickSort() method to sort array
quickSort(theArray, first, last);
cout << “Sorted List: n” << endl;
for(int count = 0; count < length; count++)
{
cout << theArray[count] << ” ” << “n”;
}
string stringArray[] = { “g”, “r”, “e”, “w”, “a”, “r”, “d”, “s”,”d”, “f”, “v”, “r”, “z”, “w”, “b”,
“q”, “p”, “a”, “z”, “s”, “l”, “p”, “u”, “d”, “x”};
length = (sizeof(stringArray)/sizeof(stringArray[0]));
first = 0;
last = length – 1;
// Display unsorted string array
cout << “List of 25 items: ” << endl;
for (int count = 0; count < length; count++)
{
cout <
}
cout << “Sort list of 25 string items: ” <<endl;
//Call quickSort() to start string array
quickSort(stringArray, first, last);
cout << “Sorted List: ” << endl;
for(int count = 0; count < length; count++)
{
cout << stringArray[count] << ” ” << “n”;
}
return 0;
}
————————————————————————————————-quickSort.cpp
#include “insertionSort.cpp”
#include
using namespace std;
template
void quickSort(ItemType theArray[], int first, int last)
{
const int MIN_SIZE = 4;
if ((last – first + 1) < MIN_SIZE)
{
cout << “Calling insertionSort with size ” << last -first + 1 << endl;
insertionSort(theArray, first, last);
}
else
{
// Create the partition: S1 | Pivot | S2
int pivotIndex = partition(theArray, first,last);
int leftSize = pivotIndex – first;
int rightSize = last – pivotIndex;
cout << “Calling quickSort with left size ” <<leftSize <<
“and right size ” << rightSize << endl;
// Sort subarrays S1 and S2
quickSort(theArray, first, pivotIndex – 1);
quickSort(theArray, pivotIndex + 1, last);
} // end if
} // end quickSort
template
int partition(ItemType theArray[], int first, int last)
{
//Choose pivot and reposition it
int mid = first + (last – first) / 2;
sortFirstMiddleLast(theArray, first, mid,last);
swap(theArray[mid], theArray[last-1]);
int pivotIndex = last – 1;
ItemType pivot = theArray[pivotIndex];
//Determine the regions S1 and S2
int indexFromLeft = first + 1;
int indexFromRight = last – 2;
bool done = false;
while(!done)
{
//Locate first entry on left that is >= pivot
while(theArray[indexFromLeft] < pivot)
{
indexFromLeft = indexFromLeft + 1;
}
//Locate first entry on the right that is <= pivot
while(theArray[indexFromRight] > pivot)
{
indexFromRight = indexFromRight – 1;
}
if(indexFromLeft < indexFromRight)
{
swap(theArray[indexFromLeft], theArray[indexFromRight]);
indexFromLeft = indexFromLeft + 1;
indexFromRight = indexFromRight – 1;
}
else
{
done = true;
}
}
//Place pivot in proper position between S1 and S2 and mark itsnew location
swap(theArray[pivotIndex], theArray[indexFromLeft]);
pivotIndex = indexFromLeft;
return pivotIndex;
}
template
void sortFirstMiddleLast(ItemType theArray[], int first, intmid, int last)
{
if (theArray[first] > theArray[mid])
{
swap(theArray[first], theArray[mid]);
}
if (theArray[mid] > theArray[last])
{
swap(theArray[mid], theArray[last]);
}
if (theArray[first] > theArray[mid])
{
swap(theArray[first], theArray[mid]);
}
}
//function to swap array elements
template
void swap(ItemType &x, ItemType &y)
{
ItemType t = x;
x = y;
y = t;
}
————————————————————————————————-inserationSort.cpp
template
void insertionSort(ItemType theArray[], int first, int last)
{
// unsorted = first index of the unsorted region,
// loc = index of insertion in the sorted region,
// nextItem = next item in the unsorted region.
// Initially, sorted region is theArray[0],
// unsorted region is theArray[1..n-1].
// In general, sorted region is theArray[0..unsorted-1],
// unsorted region theArray[unsorted..n-1]
for (int unsorted = first + 1; unsorted <= last;unsorted++)
{
// At this point, theArray[first..unsorted-1] is sorted.
// Find the right position (loc) intheArray[first..unsorted]
// for theArray[unsorted], which is the first entry in the
// unsorted region; shift, if necessary, to make room
ItemType nextItem = theArray[unsorted];
int loc = unsorted;
while ((loc > first) && (theArray[loc – 1] >nextItem))
{
// Shift theArray[loc – 1] to the right
theArray[loc] = theArray[loc – 1];
loc–;
} // end while
// At this point, theArray[loc] is where nextItem belongs
theArray[loc] = nextItem; // Insert nextItem into sortedregion
} // end for
} // end insertionSort
Expert Answer
Answer to C++. Difficulty with quickSort function. Code will not run quickSort function. The code I’m having trouble with is in bo… . . .
OR
