Based on the array named B in the figure below, write the Quick sort partition work trace for cut = partition(B,0,4) until the first cut point by using the item at middle index (the middle value) 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. THE [0] [1] [2] [3] [4] В 21 14 46 35 67 Fill in the blanks to show the work trace for cut = partition(B,0,4). Current value of bottom and top %3D bottom = top = pivot Array index [0] [1] [2] [3] [4] Array item Current value of bottom and top bottom = top = Array index [0] [1] [2] [3] [4] Array item Current value of bottom and top bottom = top = cutPoint = Recursive function and array value after cutpoint is returned. quickSort(B, quickSort(B,
Based on the array named B in the figure below, write the Quick sort partition work trace for cut = partition(B,0,4) until the first cut point by using the item at middle index (the middle value) 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. THE [0] [1] [2] [3] [4] В 21 14 46 35 67 Fill in the blanks to show the work trace for cut = partition(B,0,4). Current value of bottom and top %3D bottom = top = pivot Array index [0] [1] [2] [3] [4] Array item Current value of bottom and top bottom = top = Array index [0] [1] [2] [3] [4] Array item Current value of bottom and top bottom = top = cutPoint = Recursive function and array value after cutpoint is returned. quickSort(B, quickSort(B,
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
Data Structure and
Fill the table only
![The following program is a Quick Sort function which consists of two functions: quicksort() and
partition().
// Quick Sort function
int partition(int T[], int first,int last)
{ int pivot, temp;
1
2
4
int loop, cutPoint, bottom, top;
pivot= T[(first+last)/2];
bottom=first; top= last;
7
loоp-1;
//always TRUE
while (loop) {
while (T[top]<pivot)
8.
9
10
11
{
top--;
}
12
while(T[bottom]>pivot)
13
{
bottom++;
}
14
if (bottom<top) {
15
temp=T[bottom];
16
T[bottom]=T[top];
17
T[top]=temp;
18
}
19
else {
20
loop=0;
21
cutPoint = top;
22
}
23
}//end while
24
return cutPoint;
25
}
26
void quickSort(dataType arrayT[],int first,int last)
{
27
28
29
int cut;
20
if (first<last){
cut = partition(T,first,last);
quickSort (T, first,cut);
21
22
23
quickSort (T, cut+1, last);
24
}
25](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fa01493b9-a316-41d9-9977-5c39eb4594b5%2F6f66f496-af03-403f-91c4-f53e87f432c1%2F904mv2q_processed.png&w=3840&q=75)
Transcribed Image Text:The following program is a Quick Sort function which consists of two functions: quicksort() and
partition().
// Quick Sort function
int partition(int T[], int first,int last)
{ int pivot, temp;
1
2
4
int loop, cutPoint, bottom, top;
pivot= T[(first+last)/2];
bottom=first; top= last;
7
loоp-1;
//always TRUE
while (loop) {
while (T[top]<pivot)
8.
9
10
11
{
top--;
}
12
while(T[bottom]>pivot)
13
{
bottom++;
}
14
if (bottom<top) {
15
temp=T[bottom];
16
T[bottom]=T[top];
17
T[top]=temp;
18
}
19
else {
20
loop=0;
21
cutPoint = top;
22
}
23
}//end while
24
return cutPoint;
25
}
26
void quickSort(dataType arrayT[],int first,int last)
{
27
28
29
int cut;
20
if (first<last){
cut = partition(T,first,last);
quickSort (T, first,cut);
21
22
23
quickSort (T, cut+1, last);
24
}
25
![Based on the array named B in the figure below, write the Quick sort partition work trace for
cut = partition(B,0,4) until the first cut point by using the item at middle index (the middle
value) 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]
21
14
46
35
67
Fill in the blanks to show the work trace for cut = partition(B,0,4).
%3D
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
[0]
[1]
[2]
[3]
[4]
Array item
Current value of bottom and top
bottom =
top =
cutPoint =
Recursive function and array value after cutpoint is returned.
quickSort(B,
quickSort(B,](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fa01493b9-a316-41d9-9977-5c39eb4594b5%2F6f66f496-af03-403f-91c4-f53e87f432c1%2Fr33vuc6_processed.png&w=3840&q=75)
Transcribed Image Text:Based on the array named B in the figure below, write the Quick sort partition work trace for
cut = partition(B,0,4) until the first cut point by using the item at middle index (the middle
value) 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]
21
14
46
35
67
Fill in the blanks to show the work trace for cut = partition(B,0,4).
%3D
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
[0]
[1]
[2]
[3]
[4]
Array item
Current value of bottom and top
bottom =
top =
cutPoint =
Recursive function and array value after cutpoint is returned.
quickSort(B,
quickSort(B,
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps with 3 images
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY