CODEWITHSUNDEEP
algorithm
Gnijuohz
Gnijuohz

Reputation: 3364

How to sort an array according to another array?

Suppose A={1,2,3,4}, p={36,3,97,19}, sort A using p as sort keys. You can get {2,4,1,3}.

It is an example in the book introducton to algorithms. It says it can be done in nlogn.

Can anyone give me some idea about how it can be done? My thought is you need to keep track of each element in p to find where it ends up, like p[1] ends up at p[3] then A[1] ends up at A[3]. Can anyone use merge sort or other nlogn sorting to get this done?

I'm new to algorithm and find it a little intimidating :( thanks for any help.

Upvotes: 1

Views: 109

Answers (2)

ulmangt
ulmangt

Reputation: 5423

Construct an index array:

i = { 0, 1, 2, 3 }

Now, while you are sorting p, make the same changes to the index array i.

When you're done, you'll have:

i = { 1, 3, 0, 2 }

Sorting two arrays takes at most twice as long as sorting one (and actually, if you're only counting comparisons you don't have to do any additional comparisons, just data swaps in two arrays instead of one), so that doesn't change the Big-O complexity of the overall sort because O( 2n log n ) = O(n log n).

Now, you can use those indices to construct the sorted A array in linear time by simply iterating through the sorted index array and looking up the element of A at that index. This takes O( n ) time.

The runtime complexity of your overall algorithm is at worst: O( n + 2n log n ) = O( n log n )

Of course you can also skip index array entirely and simply treat the array A in the same way, sorting it along side p.

Upvotes: 2

Jack
Jack

Reputation: 133567

I don't see this difficult, since complexity of a sorting algorithm is usually measured on number of comparisons required you just need to update the position of elements in array A according to the elements in B. You won't need to do any comparison in addition to ones already needed to sort B so complexity is the same.

Every time you move an element, just move it in both arrays and you are done.

Upvotes: 1

Related Questions