Based on the array named dataQ in the figure below, write the Quick sort partition work trace for cut = partition(dataQ,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. %3D [0] [1] [2] [3] [4] dataQ 16 11 62 13 45 Fill in the blanks to show the work trace for cut = partition(dataQ,0,4). %3D
Based on the array named dataQ in the figure below, write the Quick sort partition work trace for cut = partition(dataQ,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. %3D [0] [1] [2] [3] [4] dataQ 16 11 62 13 45 Fill in the blanks to show the work trace for cut = partition(dataQ,0,4). %3D
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
Please give direct answers
![Based on the array named dataQ in the figure below, write the Quick sort partition work trace
for cut = partition(dataQ,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]
dataQ
16
11
62
13
45
Fill in the blanks to show the work trace for cut = partition(dataQ,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
[o]
[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(dataQ,
quickSort(dataQ,](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fa01493b9-a316-41d9-9977-5c39eb4594b5%2F77942c5c-4820-42f9-85f6-6eac3cc1646b%2Fjbqwp6e_processed.png&w=3840&q=75)
Transcribed Image Text:Based on the array named dataQ in the figure below, write the Quick sort partition work trace
for cut = partition(dataQ,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]
dataQ
16
11
62
13
45
Fill in the blanks to show the work trace for cut = partition(dataQ,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
[o]
[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(dataQ,
quickSort(dataQ,
![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;
2
3
4
int loop, cutPoint, bottom, top;
5
pivot= T[0];
6
bottom=first; top= last;
7
loop=1;
//always TRUE
while (loop) {
8.
10
while (T[top]>pivot)
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
}
}//end while
return cutPoint;
23
24
25
}
26
void quickSort(dataType arrayT[],int first,int last)
{
27
28
29
int cut;
20
if (first<last){
21
cut = partition(T, first,last);
22
quickSort(T, first,cut);
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%2F77942c5c-4820-42f9-85f6-6eac3cc1646b%2F714688_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;
2
3
4
int loop, cutPoint, bottom, top;
5
pivot= T[0];
6
bottom=first; top= last;
7
loop=1;
//always TRUE
while (loop) {
8.
10
while (T[top]>pivot)
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
}
}//end while
return cutPoint;
23
24
25
}
26
void quickSort(dataType arrayT[],int first,int last)
{
27
28
29
int cut;
20
if (first<last){
21
cut = partition(T, first,last);
22
quickSort(T, first,cut);
23
quickSort (T, cut+1, last);
24
}
25
}
Expert Solution
![](/static/compass_v2/shared-icons/check-mark.png)
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 2 steps
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
Recommended textbooks for you
![Computer Networking: A Top-Down Approach (7th Edi…](https://www.bartleby.com/isbn_cover_images/9780133594140/9780133594140_smallCoverImage.gif)
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…](https://www.bartleby.com/isbn_cover_images/9780124077263/9780124077263_smallCoverImage.gif)
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)](https://www.bartleby.com/isbn_cover_images/9781337569330/9781337569330_smallCoverImage.gif)
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…](https://www.bartleby.com/isbn_cover_images/9780133594140/9780133594140_smallCoverImage.gif)
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…](https://www.bartleby.com/isbn_cover_images/9780124077263/9780124077263_smallCoverImage.gif)
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)](https://www.bartleby.com/isbn_cover_images/9781337569330/9781337569330_smallCoverImage.gif)
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](https://www.bartleby.com/isbn_cover_images/9781337093422/9781337093422_smallCoverImage.gif)
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
![Prelude to Programming](https://www.bartleby.com/isbn_cover_images/9780133750423/9780133750423_smallCoverImage.jpg)
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
![Sc Business Data Communications and Networking, T…](https://www.bartleby.com/isbn_cover_images/9781119368830/9781119368830_smallCoverImage.gif)
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY