Quicksort

A) Use the partitioning idea of quicksort to give an algorithm that finds the median element of an array of n integers in expected O(n) time. (Hint: must you look at both sides of the partition?)

B) Write a Java program to demonstrate how the above algorithm can find the median element of the array A. in O(n) time. A= [1,5,9,7,20,22,22,6,8,3,2,1,4,9]