Thank you for your helpful answerIts necessary for you to pa

Thank you for your helpful answer!(It\'s necessary for you to pay attention to the given information)

The following is a quick sort algorithm in C++. Answer the following questions regarding this algorithm.//sort A[s..e - 1] void quicksort (int A[], int s, int e) {if (e - s

Solution

1)

2)

Choosing a random pivot minimizes the chance that you will encounter worst-case O(n²) performance (always choosing first or last would cause worst-case performance for nearly-sorted or nearly-reverse-sorted data). Choosing the middle element would also be acceptable in the majority of cases.

Also, if you are implementing this yourself, there are versions of the algorithm that work in-place (i.e. without creating two new lists and then concatenating them).

It depends on your requirements. Choosing a pivot at random makes it harder to create a data set that generates O(N^2) performance. \'Median-of-three\' (first, last, middle) is also a way of avoiding problems. Beware of relative performance of comparisons, though; if your comparisons are costly, then Mo3 does more comparisons than choosing (a single pivot value) at random. Database records can be costly to compare.

down vote

It depends on your requirements. Choosing a pivot at random makes it harder to create a data set that generates O(N^2) performance. \'Median-of-three\' (first, last, middle) is also a way of avoiding problems. Beware of relative performance of comparisons, though; if your comparisons are costly, then Mo3 does more comparisons than choosing (a single pivot value) at random. Database records can be costly to compare.