<p>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:</p>

<pre><code>for(i=0; i&lt;n; i++) {
 C[P[i]] = A[i];
}
</code></pre>

<p>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:</p>

<pre><code>B = array(1..n);
sort(B, cmp_func);
</code></pre>

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

<p>Sorry for my lame pseudocode, but I think it's understandable.</p>

CC BY-SA 3.0
2011-10-20T00:17:09.293Z
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)$).
pbaren
CC BY-SA 3.0
2011-10-20T00:23:07.987Z
I think your pseudocode works, but it's not in place (it requires a second array $B$; that is $O(n)$ space).
pbaren
CC BY-SA 3.0
2011-10-20T09:24:07.607Z
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).
Gopi
CC BY-SA 3.0
2011-10-20T09:34:19.910Z
(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.)
Gopi
CC BY-SA 3.0
2011-10-20T11:42:59.657Z
I see. My answer was meant to point out that you can't sort in O(n), unless there's a pretty tight bound on t. As for the O(n) additional space - your own link on IPS does provide I believe the most effective algorithm if you want to replace A with B (I misunderstood you on that count, that you want _another_ array B).
K.Steff
CC BY-SA 3.0
2011-10-21T07:47:31.017Z
@Gopi Maybe I am missing something but, for your proposed $O(n^2)$ algorithm, how do you differentiate the new values (e.g. the "1" you put in place of the minimum) from the original values in the array?
pbaren
CC BY-SA 3.0
2011-10-21T09:02:20.283Z
@pbaren: You put negative values :) ($-n$ to $-1$), and then you update :).
Gopi
CC BY-SA 3.0
2011-10-21T09:08:28.443Z
(and if you had negative values to begin with, you add $-$(the minimal value) to every integer.)
Gopi
CC BY-SA 3.0
2011-10-21T20:47:35.023Z
Mhh, I understand your solution, but using negative values seems like a covert way of having $n$ extra bits.
pbaren
CC BY-SA 3.0
2011-10-22T09:29:38.943Z
@pbaren, clearly $log(n)$ (the size of the negative values) is smaller or equal than $t$ (the size of the existing values): else you can show that you cannot do it in less space. Then since you *replace* a value of the initial array by an integer between $-n$ and $-1$, you do not add extra space.
Gopi
CC BY-SA 3.0
2011-10-26T18:48:52.497Z
@Gopi, the author means that -n might not be in the range of numbers that you can fit in a cell of the array A. E.g. unsigned int can't handle -20 without an extra bit for the sign. n cells, therefore n extra bits. Thus I, too, believe you're adding n bits.
K.Steff
CC BY-SA 3.0
2011-10-26T18:55:17.333Z
@Gerish, I see what you mean, did not think of this. Then simply adding +n to every integer of the array as a first step would not work either.
Gopi
CC BY-SA 3.0
2011-10-26T21:56:59.180Z
@Gopi:  Your first step could be to linearly translate your set so the minimum value in it becomes the minimum number you can represent in your t-bit scale.  This would guarantee no extra storage.
Briguy37
CC BY-SA 3.0
2011-10-19T23:32:51.510Z
2011-10-19T23:32:51.510Z
K.Steff
<p><em>Problem:</em> 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".</p>

<p>For instance:</p>

<pre><code>A = 7 7 2 5 9
B = 3 4 1 2 5
B = 4 3 1 2 5 -- a second "non stable" possibility
</code></pre>

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

<p>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.</p>

<p>A. Maus, <em><a href="http://www.nik.no/2008/06-Maus.pdf" rel="nofollow">IPS, sorting by transforming an array into its own sorting
permutation with almost no space overhead</a></em>, solves a related problem; but it seems that the method approaches standard bucket sorting, requiring $O(n)$ space, as $\log_2 n$ approaches $t$.</p>

CC BY-SA 3.0
2011-10-19T15:11:46.560Z
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..)
Gopi
CC BY-SA 3.0
2011-10-20T00:19:33.610Z
I think you are right, thanks. [Fixed that]
pbaren
<ds.algorithms>
Algorithm to "scale" an array in place
pbaren
# Algorithm to "scale" an array in place

(Asked by: username_0 on 2011-10-19)

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

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: 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..)  
> **username_0**: I think you are right, thanks. [Fixed that]  

---

## 1 answers

### Answer by username_2 on 2011-10-19. Score: 1

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

> **Comments:**
> **username_0**: 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)$).  
> **username_0**: I think your pseudocode works, but it's not in place (it requires a second array $B$; that is $O(n)$ space).  
> **username_1**: 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).  
> **username_1**: (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.)  
> **username_2**: I see. My answer was meant to point out that you can't sort in O(n), unless there's a pretty tight bound on t. As for the O(n) additional space - your own link on IPS does provide I believe the most effective algorithm if you want to replace A with B (I misunderstood you on that count, that you want _another_ array B).  
> **username_0**: @Gopi Maybe I am missing something but, for your proposed $O(n^2)$ algorithm, how do you differentiate the new values (e.g. the "1" you put in place of the minimum) from the original values in the array?  
> **username_1**: @pbaren: You put negative values :) ($-n$ to $-1$), and then you update :).  
> **username_1**: (and if you had negative values to begin with, you add $-$(the minimal value) to every integer.)  
> **username_0**: Mhh, I understand your solution, but using negative values seems like a covert way of having $n$ extra bits.  
> **username_1**: @pbaren, clearly $log(n)$ (the size of the negative values) is smaller or equal than $t$ (the size of the existing values): else you can show that you cannot do it in less space. Then since you *replace* a value of the initial array by an integer between $-n$ and $-1$, you do not add extra space.  
> **username_2**: @Gopi, the author means that -n might not be in the range of numbers that you can fit in a cell of the array A. E.g. unsigned int can't handle -20 without an extra bit for the sign. n cells, therefore n extra bits. Thus I, too, believe you're adding n bits.  
> **username_1**: @Gerish, I see what you mean, did not think of this. Then simply adding +n to every integer of the array as a first step would not work either.  
> **username_3**: @Gopi:  Your first step could be to linearly translate your set so the minimum value in it becomes the minimum number you can represent in your t-bit scale.  This would guarantee no extra storage.  

---

