Suppose I have two lists of N 3 by 3 vectors of integers.
I need to find a quick way (say of running time at most N^(1+epsilon)) to find the vectors of the first list that have the same 1st coordinate with a vector of the second list.
Of course, I could do the following naive copmarison:
for u in list_1 do
for v in list_2
if u equals v then
print u;print v;
end if;end for; end for;
This, however, would require N^2 loops.
I feel that sorting the two lists according to their first coordinate and then look up for collisions is perhaps a fast way. Bubbleshort, etc., would probably take logN time, but I can't really see how to code the search for collision between the sorted lists.
Any help would be appreciated.