Calculate how many comparisons are needed in a quicksort of the list [23, -4, 2,

Question

Calculate how many comparisons are needed in a quicksort of the list [23, -4, 2, 31, 21] (in your calculations - at any time in the sort where you must choose a pivot, that pivot should be the left-most element of the current (sub)list Calculate how many comparisons are needed in a quicksort of the list [23, -4, 2, 31, 21] (in your calculations - at any time in the sort where you must choose a pivot, that pivot should be the left-most element of the current (sub)list Calculate how many comparisons are needed in a quicksort of the list [23, -4, 2, 31, 21] (in your calculations - at any time in the sort where you must choose a pivot, that pivot should be the left-most element of the current (sub)list

Explanation / Answer

Given list: 23   -4   2   31   21
Select the pivot: 23.
23 >= 23   Yes.
23 >= -4   Yes.
23 >= 2       Yes.
23 >= 31   No.
Now, starting from right end.
23 < 21       No.
So, after 5 comparisons, exchange 23, and 21.
23   -4   2   21   31
23 >= 21   Yes.
23 >= 31   No.
23 < 31       Yes.
23 < 21       No.
So, the cumulative number of comparisons: 5 + 4 = 9.
As the indices crossed, exchange pivot with hi, i.e., 23.

So, the new list is:
21   -4   2   23   31

Now, 23 is in place.
Now the new list to be processed is:
21 -4 2
Select the pivot: 21.
21 >= 21   Yes.
21 >= -4   Yes.
21 >= 2       Yes.
Now low going beyond bound. So, stop there.
21 < 2       No.
So, the cumulative number of comparisons: 9 + 4 = 13.
As the indices crossed, exchange pivot with hi, i.e., 2.

So, the new list is:
2   -4   21   23   31

Now 21 is in place.
Now the new list to be processed is:
2 -4
Select the pivot: 2.
2 >= 2   Yes.
2 >= -4   Yes.
Now low going beyond bound. So, stop there.
2 < -4   No.
So, the cumulative number of comparisons: 13 + 3 = 16.
As the indices crossed, exchange pivot with hi, i.e., -4.

So, the new list is:
-4   2   21   23   31

Now 2 is in place.
Now the new list to be processed is:
-4
Select the pivot: -4
As the list is single element no comparisons required.

Now -4 is in place.
Now the new list to be processed is:
31.
Select the pivot: 31
As the list is single element no comparisons required.

Now 31 is in place.

Finally the fully processed list is:
-4   2   21   23   31, and the number of comparisons made is: 16.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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