Sorting of arrays based on another array

I have two arrays:

data_array=[4.4, 7.2, 10.1, 1.1, 5.5, 8.3, 2.2, 6.2, 3.3, 9.1, 1.3]

test_array=[2, 5, 9, 4, 10, 8, 7, 3, 6, 1, 1]

I need the output_array = [2.2, 5.5, 9.1, 4.4, 10.1, 8.3, 7.2, 3.3, 6.2, 1.1, 1.3]

i.e., I need to arrange the data_array based on each element wise smallest difference of the two arrays in a unique manner (meaning: in the example test_array, value '1' is present twice whoes smallest difference->0.1 with values of data_array, hence 1.1 in output array, but for second value '1' in the test_array it should take the next smallest difference-> 0.3, hence 1.3 in output array)

This is an example. I want to execute this for arrays of larger lengths (in thousands/millions)

Thank you in advance.

[Dyuman Joshi]

This takes around 6.91 sec to run for 1e5 elements on here -

da=[4.4, 7.2, 10.1, 1.1, 5.5, 8.3, 2.2, 6.2, 3.3, 9.1, 1.3];
temp=da;
ta=[2, 5, 9, 4, 10, 8, 7, 3, 6, 1, 1];

n=numel(ta);
y=zeros(1,n);
for k=1:n
    [~,y(k)]=min(abs(temp-ta(k)));
    temp(y(k))=NaN;
end
da(y)

ans = 1×11

2.2000 5.5000 9.1000 4.4000 10.1000 8.3000 7.2000 3.3000 6.2000 1.1000 1.3000

Answer 1

[Dinesh]

Hi Niranjan!

I tried reproducing the problem on my side. Since you don't want to repeat the values in data_array we must modify the elements of data_array accordingly. One easy way to solve this problem is.

1. for every element in test_array
2. Iterate over the data_array to find minimum difference.
3. Make that element of data_array to be infinity of Not a number.

data_array=[4.4, 7.2, 10.1, 1.1, 5.5, 8.3, 2.2, 6.2, 3.3, 9.1, 1.3]; 
% copying the data array so that we have our original with us  
data_array_copy=data_array; 
test_array=[2, 5, 9, 4, 10, 8, 7, 3, 6, 1, 1]; 
n=numel(test_array); 
% array to store the indices of the nearest values 
indices = 1: n; 
for k=1:n 
    % abs(data_array_copy - test_array(k)) will give the difference array 
    % and in that difference array we find the minimum index 
    % Note we need the index because we also have to mark the element in 
    % data_array as NaN 
    [~,indices(k)]=min(abs(data_array_copy-test_array(k))); 
    data_array_copy(indices(k))=NaN; 
end 
data_array(indices) 

ans = 1×11

2.2000 5.5000 9.1000 4.4000 10.1000 8.3000 7.2000 3.3000 6.2000 1.1000 1.3000

Time complexity would be O (n ^ 2)

Space complexity would be O (n)

We can solve the problem in O (n * log n) with advanced data structures like height balanced Binary search trees and complex code. So, O (n ^ 2) is more reasonable approach for this case.

Hope this helps.