Java A 16 element array stores the integers is to be sorted using the Quicksort.

Question

Java A 16 element array stores the integers is to be sorted using the Quicksort.

a. Using the formulas presented in Table 8.6, how many comparisons would be made to sort the 16 items.

b. Using the formulas presented in Table 8.6, how many swaps would be made to sort the16 items.

Table 8.6 Performance of the Quicksort Algorithm Memory Overhead Range Bytes Speed Range Effort Algorithm Binary Tree fast/slow Comments high 8n Fast for random data, slow for already sorted data O(nlogz")/O() Highest overhead. Bubble very fast/slow O(n)O(n2) Fast for data almost sorted in ascending order. Slow for most data sets. lowest 0

Explanation / Answer

a). Number of comparisons, using table, for sorting 16 elements using quick sort will be 1.45nlogn, where n is number of items

= 1.45*16*4 = ceil(92.8) = 93

b). number of swaps for 16 elements will be 0.25SE

                                                   = 0.25 * 16log16

                                                   = 23(appr.)

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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