13- Given the following numbers show the pivot and mark the two arrays that will

Question

13- Given the following numbers show the pivot and mark the two arrays that will result after the partition. For each new array show the pivot and the new partitions that will result. Assume ascending sort. 17 6 12 10 8 16 25 20 2 First after itis partitioned) Call the left partition array1 and partition and circle pivot (show two arrays the right partition array2. Show your work! What is the Pivot and partitions for array1: What is the Pivot and partitions for array2: 14- Given the following numbers show the values of the array after pass-1 and pass-2. 12 10 8 16 25 20 2 4 17 6 Pass-1: Pass-2:

Explanation / Answer

Given list: 12   10   8   16   25   20   2   4   17   6

First partition and circle pivot (show two arrays after it is partitioned) - Call the left
partition array1, and right partition array2. Show your work.
Select the pivot: 12.
12 >= 12   Yes.
12 >= 10   Yes.
12 >= 8   Yes.
12 >= 16   No.
Now, starting from the right end.
12 < 6   No.
Exchange 16, and 6.
Now, the list is:   12   10   8   6   25   20   2   4   17   16
12 >= 6   Yes.
12 >= 25   No.
12 < 16   Yes.
12 < 17   Yes.
12 < 4   No.
Exchange 25, and 4.
Now, the list is:   12   10   8   6   4   20   2   25   17   16
12 >= 4   Yes.
12 >= 20   No.
12 < 25   Yes.
12 < 2   No.
Exchange 20, and 2.
Now, the list is:    12   10   8   6   4   2   20   25   17   16  
12 >= 2       Yes.
12 >= 20   No.
12 < 20   Yes.
12 < 2   No.
As the indices crossed, exchange pivot with high index, i.e., 2.
So, the new list is:   2   10   8   6   4   12   20   25   17   16
And now array1 is: 2   10   8   6   4
And array2 is:    20   25   17   16

What is the Pivot and partitions for array 1:
The pivot for array1 is: 2.
2 >= 2       Yes.
2 >= 10       No.
2 < 4       Yes.
2 < 6       Yes.
2 < 8       Yes.
2 < 10       Yes.
2 < 2       No.
As the indices crossed, the partition is high index, i.e., 0.

What is the Pivot and partisions for array 2:
The pivot for array2 is: 20.
20 >= 20   Yes.
20 >= 25   No.
20 < 16   No.
Exchange 25, and 16.
Now the list is: 20   16   17   25
20 >= 16   Yes.
20 >= 17   Yes.
20 >= 25   No.
20 < 25   Yes.
20 < 17   No.
As the indices crossed, the partition is high index, i.e., index of 17, i.e., 8.

The values after pass 1:   2   10   8   6   4   12   20   25   17   16
The values after pass 2:   2   10   8   6   4   12   20   25   17   16
This is because, in pass2, the pivot is 2, and it is already in place, so, no change.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.