Sorting an array based on comparison with another array of same elements in different order

Question

Given two arrays

a[] = {1,3,2,4} 
b[] = {4,2,3,1}

both will have the same numbers but in different order. We have to sort both of them. The condition is that you cannot compare elements within the same array.

I don't quite understand. Are you transforming b until it has the same order as a? In which case, aren't you always just returning a? — Gian
– Gian, Commented Sep 1, 2011 at 17:17
If the interview questions were like this, I'd pass up the job. Really. — spender
– spender, Commented Sep 1, 2011 at 17:20
Come on, this is not the weirdest interview questions at all. Just accept the reality. — Mu Qiao
– Mu Qiao, Commented Sep 2, 2011 at 9:23
@Mu Qiao - it was weird before it was fixed up by an editor prior to your viewing. — hatchet - done with SOverflow
– hatchet - done with SOverflow, Commented Sep 2, 2011 at 12:57

Mu Qiao · Accepted Answer · 2011-09-02 07:27:42Z

5

I can give you an algorithm of O(N*log(N)) time complexity based on quick sort.

Randomly select an element a1 in array A
Use a1 to partition array B, note that you only have to compare every element in array B with a1
Partitioning returns the position b1. Use b1 to partition array A (the same as step 2)
Go to step 1 for the partitioned sub-arrays if their length are greater than 1.

Time complexity: T(N) = 2*T(N/2) + O(N). So the overall complexity is O(N*log(N)) according to master theorem.

edited Sep 2, 2011 at 7:27

answered Sep 2, 2011 at 2:11

Mu Qiao

7,1271 gold badge34 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

dcn · Accepted Answer · 2011-09-01 17:37:49Z

1

Not sure I understood the question properly, but from my understanding the task is a follows:

Sort a given array a without comparing any two elements from a directly. However we are given a second array b which is guaranteed to contain the same elements as a but in arbitrary order. You are not allowed to modify b (otherwise just sort b and return it...).

In case the elements in a are distinct this is easy: for every element in a count how many elements in b are smaller. This number gives us the (zero based) index in a sorted order.

The case where elements are not necessarily distinct is left to the reader :)

answered Sep 1, 2011 at 17:37

dcn

4,4693 gold badges32 silver badges40 bronze badges

2 Comments

shreyasva Over a year ago

Right good working solution. It's O(n^2). The solutions expected was to be in O(nlogn)

dcn Over a year ago

Of Course you could construct a BST of b to get it to O(nlogn) but that kind of is the same as sorting b right away...

Collectives™ on Stack Overflow

Sorting an array based on comparison with another array of same elements in different order

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related