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?

  • 1
    The 3rd paragraph is hard to understand. Could you improve it to make it more clear ? Commented Aug 12, 2013 at 16:04
  • 3
    Most library Sort() functions that I'm aware of let you provide your own Compare(a,b) function. That would let you sort (for example) a list of strings by length instead of alphabet. Commented Aug 12, 2013 at 16:15
  • 1
    What are you going to do if multiple elements are equally "close" to one of your reference elements? What if one element is equally close to two different reference elements?
    – TMN
    Commented Aug 12, 2013 at 16:15
  • 3
    Can you add some short examples of what arrays a and w might look like before and after processing? Commented Aug 12, 2013 at 16:33
  • 1
    This looks more like matching than sorting Commented Aug 12, 2013 at 16:53

3 Answers 3

  • 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)

  • +1: Better than my answer.
    Commented Aug 13, 2013 at 10:01
  • That'll work. The key is that the current tree node defines one endpoint of a fully-closed interval, and either the left or right child defines the other endpoint of the interval. The closest value will be found somewhere in that interval. Actually, it will either be the current node, the child, or somewhere in subtree "between" the node and child. (I.e., in the subsequence between the node value and the child node value, in an inorder traverse.) Commented Aug 13, 2013 at 12:27
  • +1 I don't think any kind of sorting algorithm has been made better than O(n log n). You just reduced my problem to that. Kudos! Marked yours as the answer for being the simplest here. Commented Aug 24, 2013 at 5:39
  • Marked as answer again for being closer to the exact algorithm. I didn't consider a self-balancing BST, or a Balance() function at all. Commented Aug 27, 2013 at 13:28

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.

  • This is what I thought of too, and I think it might even be faster than Dukeling's :)
    – amara
    Commented Aug 13, 2013 at 15:01
  • @sparkleshy: definitely faster. The real questions are the fine points in how a aligns with w. Our solution provides a better overall alignment, the other aligns the first elements in a perfectly and fits the last ones in however it can. Commented Aug 13, 2013 at 15:51
  • Both would be the same order since we're sorting numerically, first. Commented Aug 24, 2013 at 5:41
  • 1
    @HameerAbbasi: If you put w back the way it was, one element at a time, that would be unsorting it. Call the resulting array w'. Use the exact same transformation on the sorted a to give a'. Now a' is what you want. If a was ( 6, 5, 4 ) and w was ( 3, 1, 2), they would , sorted, be (4, 5, 6) and ( 1, 2, 3 ). Now the third in w becomes the first, so the third in the new a becomes the first, the second the second, etc. And you get ( 6, 4, 5 ) in a'. It's simpler than it sounds (when I explain it). You just reorder a so it uses w's order. Commented Aug 24, 2013 at 18:01
  • 1
    @HameerAbbasi: To answer your previous question about both being the same order: if w is ( 6, 7, 8 ) and a is ( 1, 2, 3 ), Dukeling's answer gives the new a as ( 3, 2, 1 ) where mine gives ( 1, 2, 3 ). Dukeling gets the very best answer for the first position, second best for the next, and so on. Mine kind of averages everything out. And if you want the good answers at the end, you might want to reverse Dukeling's algorithm. Commented Aug 24, 2013 at 19:08

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!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.