Subject: Data Strucure and Algorithm in C++ Please fill in the blank fields in the table in the image only Question: The following program is a Quick Sort function which consists of two functions: quicksort() and partition() . Code: // Quick Sort function int partition(int T[], int first,int last) { int pivot, temp; int loop, cutPoint, bottom, top; pivot= T[0]; bottom=first; top= last; loop=1; //always TRUE while (loop) { while (T[top]>pivot) { top--; } while(T[bottom]
Subject: Data Strucure and
Please fill in the blank fields in the table in the image only
Question:
The following program is a Quick Sort function which consists of two functions: quicksort() and partition() .
Code:
// Quick Sort function
int partition(int T[], int first,int last)
{ int pivot, temp;
int loop, cutPoint, bottom, top;
pivot= T[0];
bottom=first; top= last;
loop=1; //always TRUE
while (loop) {
while (T[top]>pivot)
{ top--; }
while(T[bottom]<pivot)
{ bottom++; }
if (bottom<top) {
temp=T[bottom];
T[bottom]=T[top];
T[top]=temp;
}
else {
loop=0;
cutPoint = top;
}
}//end while
return cutPoint;
}
void quickSort(dataType arrayT[],int first,int last)
{
int cut;
if (first<last){
cut = partition(T,first,last);
quickSort(T, first,cut);
quickSort (T, cut+1, last);
}
}
Based on the array named T in the figure below, write the Quick sort partition work trace for cut = partition(T,0,4) until the first cut point by using the item at first index as pivot. In the diagram given, show the following:
i) The movement of bottom and top.
ii) The swapping process.
iii) The cutPoint and the new 2 parts array for the next recursive call.
![[0]
[1]
[2]
[3]
[4]
9
7
10
5
Fill in the blanks to show the work trace for cut = partition(T,0,4).
Current value of bottom and top
bottom =
top =
pivot =
Array index
[0]
[1]
[2]
[3]
[4]
Array item
Current value of bottom and top
bottom =
top =
Array index
Array item
[0]
[1]
[2]
[3]
[4]
Current value of bottom and top
bottom =
top =
cutPoint =
Recursive function and array value after cutpoint is returned.
quickSort(T,
quickSort(T,
LO](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fa01493b9-a316-41d9-9977-5c39eb4594b5%2F06ccb2a1-715e-4380-8309-a768837d3c8c%2F7nctsek_processed.jpeg&w=3840&q=75)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
