2
$\begingroup$

You have to sort a given array (assuming nothing more than the elements are totally ordered) which is write once read many (WORM) in constant space i.e using a constant number of variables.

So, my naive approach was to fix the position of one element at a time. But in what order? If I do it first to last then the information of the element of the index where I placed the first element is lost. So, if I start with the first element, then try to fix the element where the first element was placed, I will eventually run into problem because I'll have to remember the relative order of the current element and the elements sorted till now.

It seems doable but I can't really figure it out. For now, I don't care about running time.

$\endgroup$
  • 1
    $\begingroup$ I don't understand your model. In particular, is the sorted array going to be in the same place as the unsorted array? Are you allowed to write to each location of the sorted array exactly once, and to the work memory an arbitrary number of times? $\endgroup$ – Yuval Filmus Mar 2 '17 at 17:15
  • $\begingroup$ @YuvalFilmus Yes, "the sorted array going to be in the same place as the unsorted array". If you think in terms of machines you have write once read many input tape and a constant space work tape. $\endgroup$ – Faustus Mar 5 '17 at 14:12
2
$\begingroup$

Here is an approach which is not too efficient in terms of running time. Suppose your array has length $n$, say $A[1],\ldots,A[n]$. Given an element of your array, you can determine its rank (i.e., the value of $k$ such that it is the $k$th smallest element), so we can assume that the array contains a permutation of $1,\ldots,n$.

Consider now the cycle induce by the element $A[1]$, that is, write $$ A[1] = x_1, A[x_1] = x_2, \ldots, A[x_\ell] = 1. $$ If $x_1 = 1$ then $1$ is already at the correct place. Otherwise, you want to modify the array so that: $$ A[1] = 1, A[x_1] = x_1, \ldots, A[x_\ell] = x_\ell. $$ Hopefully you can see how to do it using constant space.

Go over all the elements $A[1],\ldots,A[n]$ in this way. Elements which you have already sorted (for example, $x_1$ in the example above) will already be at the correct place, so you will only modify each cycle once. In other words, you will only write to each position once.

$\endgroup$
  • $\begingroup$ Your algorithm for a permutation is correct. However, I guess in this case sorting any array and sorting a permutation isn't the same as you can write only once so your reduction will use up that write opportunity. $\endgroup$ – Faustus Mar 5 '17 at 14:21
  • $\begingroup$ It works for an arbitrary array, as long as all entries are distinct. If you are careful enough you can handle non-distinct elements as well. You can determine the rank of an element "on-line", without writing it on the write-only tape. $\endgroup$ – Yuval Filmus Mar 5 '17 at 14:50

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.