implement algorithm using any programming languages.

median_of_medians

QuickSelectAdaptive

implement QuickSelectAdaptive algorithm and compare it with median_of_medians. Run 100 cases of input sizes of 10⁴, 10⁵, and 10⁶ on both algorithms to check whether QuickSelectAdaptive runs much faster than median_of_medians.

Input: a list of integers - A, and an integer j Output: an integer Example: A 11, 58, -3, 100, 2000, 2 it returns 11 (the 2nd smallest element in A) median of medians(A, i): L1: / divide A into sublists of len 5 2: sublists [A[1:j+5] for j in rangea, len(A), 5)] L medians-[sorted (sublist) len(sublist)/2] for sublist in sublists] 4: if len(medians) 5 L5 : then pivot sorted(medians)[len(medians)/2] else //the pivot is the median of the medians pivot - median of medians (medians, len (medians)/2) 7: //partitioning step 8: low = [j for j in A if j pivot] L10 : k len(low) = return median of medians (lou,i) return median of medians (high,i-k-1) return A[pivot] L12 else if i > k: L13: L14 : else // #pivot k Data: A, k with 0 S k 5|Al then 7|pMEDIANOFMAXIMA(A, k); s else 9 | p( MEDIANOFNINTHERS(A); 10 en if p = k then return; if p > k then 12 13 14 16 en 18 end