7
$\begingroup$

Problem: transform an array $A$ of $n$ natural numbers (of $t$-bits) into an array $B$, which is a permutation of $\{1, ..., n\}$ with the property that, whenever $B[i] \leq B[j]$ holds, $A[i] \leq A[j]$ holds. Call this operation "scaling".

For instance:

A = 7 7 2 5 9
B = 3 4 1 2 5
B = 4 3 1 2 5 -- a second "non stable" possibility

Assuming $n$ can be represented in $t$ bits, is there a way of scaling an array in place?

The time and space complexity should be as close to $O(n)$ and $O(1)$ as possible, with a $O(\log n)$ factor being probably acceptable.

A. Maus, IPS, sorting by transforming an array into its own sorting permutation with almost no space overhead, solves a related problem; but it seems that the method approaches standard bucket sorting, requiring $O(n)$ space, as $\log_2 n$ approaches $t$.

$\endgroup$
  • $\begingroup$ Shouldn't it be "whenever $B[i]\leq B[j]$ holds, $A[i]\leq A[j]$ holds" instead of "whenever $A[i]\leq A[j]$ holds, $B[i]\leq B[j]$ holds"? (otherwise if for $i\neq j$, $A[i]=A[j]$, $B[i] \leq B[j]$ and $B[i] \geq B[j]$, but $B$ is a permutation so it is not possible..) $\endgroup$ – Gopi Oct 19 '11 at 15:11
  • $\begingroup$ I think you are right, thanks. [Fixed that] $\endgroup$ – pbaren Oct 20 '11 at 0:19
1
$\begingroup$

Correct me if I'm wrong, but given this is possible with O(n) time, then you can build the sorted array in O(n) time, too:

for(i=0; i<n; i++) {
 C[P[i]] = A[i];
}

If so, there's no way this can be done in O(n), since sorting is O(n.log(n)) at least. When you take that into account, there are many O(n.log(n)) sorting algorithms, that can be easily fitted for your purpose and you can implement it this way:

B = array(1..n);
sort(B, cmp_func);

where cmp_func(int a, int b) compares A[a] and A[b] instead of a and b.

Sorry for my lame pseudocode, but I think it's understandable.

$\endgroup$
  • $\begingroup$ It's true that you can sort in $O(n)$ time, but in this case we aren't working with an abstract data type which only allows comparisons, but with $t$-bit integers. Bucket sorting also allows sorting $t$-bit integers in $O(n)$ time. (I only mentioned one side of the inequality, but, in the context I was thinking of, $t \in \Theta(\log_2 n)$). $\endgroup$ – pbaren Oct 20 '11 at 0:17
  • 1
    $\begingroup$ I think your pseudocode works, but it's not in place (it requires a second array $B$; that is $O(n)$ space). $\endgroup$ – pbaren Oct 20 '11 at 0:23
  • 1
    $\begingroup$ The difficulty of this question is indeed to keep a $O(nlog^{k} n)$ time complexity, however, while making a $O(log^{j}(n))$ space complexity. This answers does not answer the question: the main difficulty of this question is the "in place" part with a low time complexity (I think it can be done with a $O(n^2)$ time complexity, but I have not been able to find a solution with a lower time-complexity). $\endgroup$ – Gopi Oct 20 '11 at 9:24
  • $\begingroup$ (BTW, when I said "I think it can be done", I meant: "it can be done": search for the minimum and replace it by 1, then do the same for the second minimum etc, then you have $O(n^2)$ time complexity and $O(1)$ space complexity.) $\endgroup$ – Gopi Oct 20 '11 at 9:34
  • 1
    $\begingroup$ Mhh, I understand your solution, but using negative values seems like a covert way of having $n$ extra bits. $\endgroup$ – pbaren Oct 21 '11 at 20:47

Your Answer

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

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