Algorithm for sorting and pairing elements of 2 arrays

Question

Hi, I am trying to configure an efficient algorithm (faster than O(n^2)) for sorting and pairing elements between 2 arrays. However this needs to work under the premise that neither array's elements can be compared to other elements in their own array.

Edit: The elements of the arrays are "sizes" which correspond to particular objects. The idea is that two parts of the same size will fit together. If we were to call the parts screws and holes a screw will only fit in a hole of the same size. However we cannot compare holes to holes or screws to screws for the purpose of this algorithm.

So I am trying to find an algorithm that will best pair together these elements of screw and hole sizes and sort them without comparing an element to elements in the same array.

Re-edit: When two elements are compared from the array we are able to know whether the screw is bigger or smaller than the hole it is compared to.

Answer 1

If you cannot compare "screws" with other "screws" or "holes" with other "holes", then neither the array of "screws" or the array of "holes" can be sorted. I think that means that you have to compare a given "screw" with each "hole" in turn in order to find a match. That's O(N^2).

There might be a better solution, but it is likely to entail changing the constraints on your problem. In particular, the constraint that says you cannot compare "screws" or "holes" is a show stopper. Without the ability to at least partially order the screws or the holes, I think you've got no alternative but to test the pairings one at a time.

EDIT

Your statement that you can determine if a "screw" is bigger or smaller than a "hole" doesn't help. Specifically, knowing that a "hole" is too small or too big doesn't help you find a "hole" that is closer in size.

[That is ... unless you sort all "holes" according to whether they are smaller, bigger or a fit for a given "screw". But that is an O(N) operation ... a bucket sort ... and you need to do that for each screw, so you are back to O(N^2). I suppose that this approach might help if you were doing this pairing process incrementally. But you didn't say that.]

Maybe the solution to this problem is to figure out an artificial ordering on the those properties of the "holes" and "screws" that determine whether they match. So for example, one might order the screws by a hash of the diameter and thread pitch.

Answer 2

Revised

Suppose that we can get one of the three outcomes when we try to fit a screw into a hole:

1. The screw is too small for the hole, such that the screw becomes loose and falls out.
2. The screw fits the hole exactly.
3. The screw is too big for the hole.

Divide-and-conquer solution.

• Stage #1
  1. Pick one screw.
  2. Use this screw to test through all holes. (requires N trials)
     • This partitions all holes into one of three cases:
       1. The hole is bigger than the test screw (A).
       2. The hole is the same size as the test screw (B).
       3. The hole is smaller than the test screw (C).
  3. Use the hole which has the same size (chosen from B) to test through all screws. (requires N trials)
     • This partitions all screws into one of three cases:
       1. The screw is bigger than the test hole (D).
       2. The screw is the same size as the test hole (E).
       3. The screw is smaller than the test hole (F).
     • Result:
       1. Any hole picked from B will fit any screw picked from E. This will be the "Pivot" of the partition. They do not require any further testing.
       2. The holes in set A and the screws in set D have diameters wider than the pivot. The holes in set C and the screws in set F have diameters narrower than the pivot.
       3. Thus, we successfully partitioned the initial problem into two smaller problems.

Analysis

• Average case: O(N log N)
• Worst case: O(N^2) because we do not know the rank of the pivot until we have finished partitioning the set using the pivot. Same analysis as QuickSort.

About a variant of the question

There is a variant of the question in which it's not possible to distinguish between loose-fit with exact fit. That is, for each test only two outcomes are possible:

• hole < screw
• hole >= screw

This variant is much much harder. I do not know if it can be solved in O(n log n) or not. (Edited)