We have n distinct keys in array A[0..n-1] that belong to an arbitrary range. The keys are comparable thus for every two keys A[i] and A[j] we can determine in one comparison which one is larger or smaller. (You may assume that n is a multiple of 4). We would like to order the n keys into four groups A_1 , A_2 , A_3 , A_4, each of size n/4, such that all the keys in A_1 are larger than those in A_2, those in A_2 are larger than those in A_3 and so on. WE DON'T care however if the keys within each of the sets are ordered (sorted). Describe a time efficient algorithm that solves this problem i.e. determines the elements of A_1 , A_2 , A_3 and A_4. Justify your answer and provide the running time of your time efficient solution using appropriate (tight) asymptotic notation. Example note. A_1 = [ 1000, 1000000 , 2000000000000, 30000000] A_2 = [ 800, 300, 501, 999 ] A_3 =[259 , 51, 99, 59] A_4 = [ 24.34, 1 , 2/3 , 10]
Its Urgent.Can anyone of you please help me solve this?
We have n distinct keys in array A[0..n-1] that belong to an arbitrary range. The keys are comparable thus for every
two keys A[i] and A[j] we can determine in one comparison which one is larger or smaller. (You may assume that n is a multiple of 4).
We would like to order the n keys into four groups A_1 , A_2 , A_3 , A_4, each of size n/4, such that all the
keys in A_1 are larger than those in A_2, those in A_2 are larger than those in A_3 and so on.
WE DON'T care however if the keys within each of the sets are ordered (sorted).
Describe a time efficient
A_1 , A_2 , A_3 and A_4. Justify your answer and provide the running time of your time efficient solution using appropriate (tight) asymptotic notation.
Example note.
A_1 = [ 1000, 1000000 , 2000000000000, 30000000]
A_2 = [ 800, 300, 501, 999 ]
A_3 =[259 , 51, 99, 59]
A_4 = [ 24.34, 1 , 2/3 , 10]
would be an acceptable solution if we had n=16 numeric-like keys as shown
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
