in python, Implement the quicksort algorithm with Lomutos pivot choice (same as Algorithm 3) Set n = 1000. Populate your input test array with random elements. (a) (22.5 points) Sort the array, and run quicksort on the sorted array (use an external routine of your language for doing the pre-sorting). Based on your results, what do you feel is this the best or worst case ?1 :-) (b) (22.5) Test quicksorts performance with the median-of-3 pivot choice, where pivot = median(A[0], A[b(n 1)/2c], A[n 1]). (Just change line 1 in the pesudo-code in the handout). Test it with the same sorted array. Are the results better this time, i.e., does it manage to avoid the worst-case?

Algorithm 3: Partition Input : A, p, r Output: Index of pivot element 1 x = A[r] 2 i = p 1 3 for j = p to r 1 do 4 if A[j] x then 5 i = i + 1 6 swap(A[i], A[j]) 7 end 8 end 9 swap(A[i + 1], A[r]) 10 return i + 1