optimized algorithm to synchronize two arrays

Question

hi... am looking for an efficient algorithm to synchronize two arrays..

Lets say a1 and a2 are two arrays given as input...

a1 - C , C++ , Java , C# , Perl

a2 - C++ , Python , Java , Cw , Haskel

output 2 arrays:

Output A1 : C , C++ , Java

Output A2 : Cw , Haskell , Python

Output A1 : 1) items common to both arrays 2) items only in a1 and not in a2

Output A2:

items only in a2

thanks in advance... raj...

Answer 1

1. Sort both arrays with an efficient sorting algorithm, complexity of O(n.log(n))
2. Build the output arrays initially empty
3. Compare the first element a1 of sorted A1 to the first element a2 of sorted A2
   • Equal means is in both arrays, put a1 into OutputA1
   • a1 < a2 means a1 is only in A1, a1 now necomes next element in sorted A1, put a1 into OutputA1
   • else a2 < a1 means a2 is only in A2, a2 now necomes next element in sorted A2, put a2 into OutputA2

Do this until you processed all elements in the sorted arrays, complexity of O(n).

Answer 2

Knuth probably said something on this problem - http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming The books are expensive, but if you have access to them, you'll probably find some wisdom in there.