Sort an array in a specific order - not ascending/descending

Question

I'm working on an algorithm that works best if the inputs are passed to it in a particular order, so I want to sort them that way. The difference is drastic enough for me to consider re-sorting the array.

Consider an array a with length n. I want to sort it the following way, and return the array of indices of a instead of the values:

I define another array w, also of length n. I want to sort such that the first element is closest to the first element of w. Then, from the rest of the elements (excluding the one already sorted), the second element is closest to the second element of w, and so on.

For example a = {5.5, 6.5, 2.4, 3.1}, w = {1, 2, 6, 5}.

2.4 is closest to 1, so output[0] = 2, the index of 2.4.

2.4 is closest to 2, but already processed, so choose 3.1, output[1] = 3.

Next come 0 and 1, in that order. 0 is chosen because it comes first, although both are equidistant.

So, output = {2, 3, 0, 1} and the sorted array would be sorted = {2.4, 3.1, 5.5, 6.5} (each index is used to find the corresponding element).

I can only think of brute-forcing this algorithm. Can there be a more efficient way to do it?

Answer 1

• Insert all elements of a into a (self-balancing) Binary Search Tree (BST) - O(n log n)

• For each element of w, lookup and remove the closest element in the BST and add it to the output - O(n log n)

  Finding the closest element in a BST is rather easy. If the element is greater than the current node's element, look right, if it's smaller, look left, if it's equal, stop. As you go down the tree, simply keep track of the closest element.

Having it return the indices instead of the element should be trivial.

Total running time - O(n log n)

Answer 2

Would this work? Sort both arrays numerically, remembering the original indexes for w so you can restore it quickly. Then use w's unsort on a. This would give you a result of {2, 3, 1, 0} rather than {2, 3, 0, 1}, but that might be a better answer, depending how you look at it, and it would be a bit faster than brute forcing it.

Answer 3

Let's take a look at the example array a:

a = {5.5, 6.5, 2.4, 3.1}

Now we know that for any number x < 2.75 the closest number in that array will be 2.4 (at index 2). Similarly, for every number x, 2.75 < x < 4.3, the closest number in that array will be 3.1 (at index 3), and so on:

upper limit        index
2.75               2
4.3                3
6.0                0
"+infinity"        1

Now, using this table finding the closest number in a for w[0] = 1 is easy. Just find the closest upper limit for 1, which is 2.75 and the corresponding index of array a is 2. (This can be optimized by using binary search.)

Since that index can be used only once, we must now alter the table by removing that entry:

upper limit        index
4.3                3
6.0                0
"+infinity"        1

Next, the closest upper limit for w[1] = 2 is 3 and after removing that the table looks like this:

upper limit        index
6.0                0
"+infinity"        1

After next step (w[2] = 6) the table has only one entry:

upper limit        index
"+infinity"        1

In this example we didn't have to remove the last entry from the table during the process. If that needs to be done, then last entry entry of the resulting table has to be updated to have the upper limit of "+infinity".

---

NOTE: I have not checked whether this algorithm actually works!