Thank you for your helpful answerIts necessary for you to pa

10. (14 pts) The following is a quick-sort algorithm in C+ Answer the following questions regarding this algorithm. void swap (int A[], int i, int j) { // sort A[s..e-1] void quicksort (int AL]. int s, int eA int temp A[i ] ; if (e - s

Solution

1. The actual code will be:-

2. The running time of the Quick Sort Algorithm depends on how the partition() method will split the input array. The value of the pivot will affect the performance of Quick Sort. The Quick Sort algorithm performs the worst when the pivot is the largest or smallest value in the array. When the pivot is the largest or smallest value in the array, the partition() step will do nothing to improve the ordering of the array elements. In particular, if the rank of the pivot (recall that this means its position in the final sorted list) is very large or very small, then the partition will be unbalanced. We will see that unbalanced partitions (like unbalanced binary trees) are bad, and result is poor running times. However, if the rank of the pivot is anywhere near the middle portion of the array, then the split will be reasonably well balanced, and the overall running time will be good. Since the pivot is chosen at random by our algorithm, we may do well most of the time and poorly occasionally. We will see that the expected running time is O(n log n).