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$.

Improve this question
$\endgroup$
2
  • $\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, 2011 at 15:11
  • $\begingroup$ I think you are right, thanks. [Fixed that] $\endgroup$
    – pbaren
    Oct 20, 2011 at 0:19

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
13
  • $\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, 2011 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, 2011 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, 2011 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, 2011 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, 2011 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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