I want to find the most optimal algorithm for finding closest ordered pairs and link them.

For example: Go thru the vector, one by one

For each one set the next according to a set of various conditions

For example, something like:

A B X C Y Z D

First we will link A to B Then when we have a look at B, we will link B to C Next when we consider X, we will link X to Y Next when we consider C, we will link C to D ... and so on

Currently someone has completed this task with some nested loops that are genuinely sub-par and it completes in O(n^2) time. Not to mention it doesn't work. What might be a better algorithm?

Here is what the current algorithm is:

for(i in list)
  while (i and j) is not linked 
     increment j
  if j is not the end
     while ++j is not the end  
       if link exists (i and j)
       break
     end while
     set link i to j
  end if
end for

I was going to write my own but I have a feeling I've seen this problem before at university and there was a simple solution to it..? Can anyone point me in the right direction please?

  • @Rob Thats it, closest pair algorithm I think, thanks – solarflare Sep 13 at 2:07
  • 1
    @Rob thanks for that. I'm going to wait in case someone else has a better solution as a divide and conquer algorithm with 2 quicksorts might in fact be overkill in my situation when there's going to be 20 conditions for the sort. – solarflare Sep 13 at 2:30
  • If you could specify which algorithm you wanted to use in your question it would narrow down the answer to a speed/complexity appropriate answer. I suggested that algorithm because you wanted an improvement over $O(n^2)$. – Rob Sep 13 at 3:03

An alternative approach could be

  1. Scan the vector and insert all elements into a self-balancing BST (AVL or Red-Black Tree etc etc, your pick) along with its index in the vector. $Node := (Value,VectorIndex)$

  2. Then you have two choices

    • Scan the vector again, and for each element, search for it in the BST, and find its successor. Link the element and its successor in the vector.
    • Do an inorder traversal of the BST and for every pair of consecutive nodes visited in the BST, link their corresponding elements in the vector.

Either way, step 1 and 2 each take $O(n\space log \space n)$, hence the total algorithm ends up with a time complexity of $O(n \space log \space n)$ and space complexity of $O(n)$.

  • I like it. But as I have been informed by the business analysts the use case will never have more than around 7 or 8 items in it so I'm going with brute force. – solarflare Sep 14 at 0:03
  • 1
    "X will never happen" might be the quickest way to shoot yourself in the foot though. – Aristu Sep 14 at 0:36
  • @solarflare just like Aristu said, never trust the fact that the use case once specified will still be enforced many years later. Its always safer to use a condition like ' if (sizeof(dataset)<threshold) then doBruteForce() else doEfficientAlgo()'. – RandomPerfectHashFunction Sep 14 at 4:44
  • I don't want to reveal the industry or use case but trust me if it did happen it would be an incredibly bizarre (and somewhat laughable) rarity. If it happens, they can wait an extra 2 seconds we don't mind. Thanks for all the tips guys, much appreciated. – solarflare Sep 14 at 5:22

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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