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

algorithmssorting

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?

Best Answer

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)

Related Solutions

Fully Stable, In-Place Unique Algorithm in O(n)

I'm not sure, but I think you need to drop the "preferably one-pass" from your description. You can do it in three passes by using the following algorithm:

Take a pass over the array, counting the number of unique items as unique_count
Allocate a new temporary array with size len(A) - unique_count
Take a second pass over the array, shifting each first instance of an item to the front of the array while copying the second instance to the first free space in the temporary array
Take a pass over the temporary array, copying each item to its final position in the input array

This is still O(n), albeit with somewhat higher constant factor per item than your original implementation.

Level order sorted binary tree from a binary tree

Sounds like you need a type of heap with some modified properties. First, use a min-heap instead of a max-heap: every node is less than the values of its children, and add a constraint that a node is greater than its siblings to the left.

One of the neat features of a heap is that it is a balanced binary tree: the depth of all leaf nodes vary by at most 1. Furthermore, leaf nodes are populated left to right. While this is not quite the same representation as you have, it makes the whole thing a ton easier.

If you take a tree with these properties and perform a level-order traversal, you can easily convert it to and from an array:

root = 6
root->left = 1 
root->right = 9
root->left->left = 8
root->left->right = 2

Level-order traversal gives the following: 6, 1, 9, 8, 2.

Note how each level takes 2^n elements in that array, where n is the depth of the nodes at that level. The root node has depth 0, so it takes 2^0 = 1 element. Next level has depth 1, so it takes 2^1 = 2 elements. This property means there is a direct correlation between a specific element in the tree and its array position.

Now perform an efficient sort on that array, and you get: 1, 2, 6, 8, 9.

Perform the reverse of the first transformation. Element 0 is the root, Elements 1 and 2 are the next level, elements 3, 4, (and 5, 6 if present) are the next level.

root = 1
root->left = 2
root->right = 6
root->left->left = 8
root->left->right = 9

If you need to maintain the fact that leaves are not populated left to right, or the tree is not balanced, you can add gaps by saying certain nodes are null and modify a sort algorithm to leave null values in-place. Not ideal, but it can allow you to leverage the properties of a heap to do this. Level-order sorting pretty much has to be done using a heap as far as I am aware (made it through a B.S. and M.S. in computer science without ever hearing or seeing another way to do this, and you know the real world doesn't care).

Best Answer

Related Solutions

Fully Stable, In-Place Unique Algorithm in O(n)

Level order sorted binary tree from a binary tree

Related Topic