Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
1  
The 3rd paragraph is hard to understand. Could you improve it to make it more clear ? –  user61852 Aug 12 '13 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. –  Dan Pichelman Aug 12 '13 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 Aug 12 '13 at 16:15
3  
Can you add some short examples of what arrays a and w might look like before and after processing? –  Dan Pichelman Aug 12 '13 at 16:33
1  
This looks more like matching than sorting –  Aaron Kurtzhals Aug 12 '13 at 16:53
show 5 more comments

3 Answers

up vote 7 down vote accepted
  • 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)

share|improve this answer
    
+1: Better than my answer. –  COME FROM Aug 13 '13 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.) –  John R. Strohm Aug 13 '13 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. –  Hameer Abbasi Aug 24 '13 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. –  Hameer Abbasi Aug 27 '13 at 13:28
add comment

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.

share|improve this answer
    
This is what I thought of too, and I think it might even be faster than Dukeling's :) –  sparkleshy Aug 13 '13 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. –  RalphChapin Aug 13 '13 at 15:51
    
Both would be the same order since we're sorting numerically, first. –  Hameer Abbasi Aug 24 '13 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. –  RalphChapin Aug 24 '13 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. –  RalphChapin Aug 24 '13 at 19:08
show 6 more comments

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!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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