2
$\begingroup$

There's an algorithm for finding the k'th smallest element in an unsorted array similar to quickselect:

kthSmallest(arr[0..n-1], k)
1) Divide arr[] into ⌈n/5⌉ groups where size of each group is 5 except possibly the last group which may have less than 5 elements.

2) Sort the above created ⌈n/5⌉ groups and find median of all groups. Create an auxiliary array 'median[]' and store medians of all ⌈n/5⌉ groups in this median array.

// Recursively call this method to find median of median[0..⌈n/5⌉-1]
3) medOfMed = kthSmallest(median[0..⌈n/5⌉-1], ⌈n/10⌉)

4) Partition arr[] around medOfMed and obtain its position. pos = partition(arr, n, medOfMed)

5) If pos == k return medOfMed
6) If pos > k return kthSmallest(arr[l..pos-1], k)
7) If pos < k return kthSmallest(arr[pos+1..r], k-pos+l-1)

The algorithm assumes that there are no repeated values.

I think that the worst case is when medOfMed is as big or as small as possible, so that it divides as unevenly as possible (although I don't know what the array would look like in that case). My idea for this was to make the medians of each subarray of five elements in a way so that when they're joined together it's as big (or small) as possible. For example: ((-10000, -1000, 1, 2, 3), (-50000, -2000, -100, 4, 5))

My classmate says that to achieve worst case results you can just fill the array with scales of length five that are increasing and has "average" values for the median and values above it, for example (-1000,-500,1,2,3) because then when it is time to sort by the median of medians you can get a number that is above the others.

I think he's wrong because at the end his median will always have to divide in groups of 2.

Who is right (if any)? Is there some other way to achieve worst case time? How can I prove this with time complexity?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.