Quick Sort Algorithm to be implemented in the specific following way (using C++)

Question

Quick Sort Algorithm to be implemented in the specific following way (using C++): Need help

Your task is to compute the total number of comparisons used to sort an array of length "m" by QuickSort. As you know, the number of comparisons depends on which elements are chosen as pivots, so we'll ask you to explore the following pivoting rule,

You should not count comparisons one-by-one. Rather, when there is a recursive call on a subarray of length m, you should simply add m?1 to your running total of comparisons. (This is because the pivot element is compared to each of the other m?1elements in the subarray in this recursive call.)

Please give the High-level idea in accordance with the following QuickSort Psuedocode:

QuickSort (array A, length n) -lf n-1 return -p ChoosePivot(A,n) -Partition A around p Recursively sort 1st part -Recursively sort 2nd part currently unimplemented ] 1st part 2nd part

Explanation / Answer

The normal quicksort pseudocode that you have written is alright.

We choose a partition at p, p = ChoosePivot(A,n), and this is done recursively in (1...p-1) and (p+1....n) as well.

So we have two arrays to be compared with the pivot element.

Let us build a class like

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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