2
$\begingroup$

Premise: Let $A := [ k(1), k(2), ..., k(n) ]$ and $B:=[ l(1), l(2), ..., l(n) ]$ be two Arrays where $k$ and $l$ are permutations. (What I'm trying to express: $A$ and $B$ contain the same elements in different orders.)

$A$ and $B$ are of different types, thus it is not allowed to mix them in the same data structure.

It is not possible to compare two elements that are from the same array with each other. However, given is an ordering $A \times B \rightarrow \{<, >, =\}$ (in words: it is possible to compare an $a \in A$ with a $b \in B$ which will tell whether $a > b$, $a = b$ or $a<b$).

There are no restrictions on space being used.

The task is to sort both arrays.

I think I have found a solution analogous to QuickSort that also has $\Theta(n~\,log\,n)$ best case and $\Theta(n^2)$ worst case time complexity.

My question: Is there an algorithm that runs in $\Theta(n~\,log\,n)$ in the worst case aswell?


My approach:

  1. Facilitate $A[1] = B[1]$ by iterating through $B[2, ..., n]$ and swapping the element that is equal to $A[1]$ to $B[1]$.

  2. Use that element as a Pivot and, in the fashion of QuickSort, go through $A[2..n]$ comparing the elements with $B[1]$ and vice versa for $B[2..n]$.

  3. Rearrange the pivot so that to the left of it there are only elements that are smaller than the Pivot and all others to the right of them. At this point it is guaranteed that

  4. Do this recursively until reaching a base case in which there is only a single element to be sorted.

Now, as far as I can see, similarly to QuickSort, in the best case we require $log~n$ layers of recursion and in each we have a total of $n$ required for recombination.

However, this has the weakness that if the input is already sorted, we will end up with quadratic runtime.

When using a D&C approach, one has to take care that the two arrays are divided so that the resulting smaller arrays still contain the same elements.

$\endgroup$
  • $\begingroup$ This is about a minor improvement of the existing approach. You do not have to do step 1 separately. Just use A[1] as a pivot to sort B, keeping track of the element in B that is equal to A[1]. (In fact, it is usually tracked automatically.) Then use B[i] that is equal to A[1] as a pivot to sort A. Of course, the existing approach has the beauty of symmetry and the advantage to be understood more easily. $\endgroup$ – Apass.Jack Nov 2 '18 at 1:25
  • $\begingroup$ Can you clarify that there is no extra memory or there is only $O(1)$ extra memory? Otherwise, suppose we just copy $A$ to a third array. Can we compare two elements in the third array? (I believe that should be disallowed. However, I would like a formal clarification from you.) $\endgroup$ – Apass.Jack Nov 2 '18 at 7:39
  • $\begingroup$ @Apass.Jack: In the original exercise, they talk about male and female screws. I abstracted that to be natural numbers, but, more precisely, elements of $A$ and $B$ would be of different types and thus could not be put into the same array for sorting. I'll clarify that in an edit and reply to your other comment later. $\endgroup$ – ngmir Nov 2 '18 at 8:08
  • $\begingroup$ @Apass.Jack I see your point about step (1). Thanks for the feedback. I've also made an edit to the question, I hope its clear now. $\endgroup$ – ngmir Nov 2 '18 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.