3
$\begingroup$

So I have an array $A$, already sorted with CountingSort. Now I reduce one randomly chosen element $j$ with $A[j]>0$ by $x \in \{1 \dots A[j]\}$. I still have the counting array $C$, since I have sorted the array with counting sort.

The question is: how can I now sort the modified array in $O(k)$?

So far: Obviously I won't need to check all the elements of $A$ again, otherwise it would be $O(n)$. I have to modify the $C$ array somehow. If you subtract $C[j+1] - C[j]$ you have the number of elements in the respective interval (like $0 - 0=0$ are 0 Elements of value 0, $1-0 = 1$ is 1 Element of value 1). But this is still only for the old array.

How can I understand which element from $A$ is reduced only by looking at $C$?

Example:

Sorted $A[4] = \{1,3,4,4\}$, reduce let`s say $j = 2$ with $A[2] = 4$ by $x \in \{1, \dots , 4\}$. Let $x = 4$ then we have $A[4] = \{1,3,0,4\}$. How can I sort it now in $O(k)$ like $A[4] = \{0,1,3,4\}$?

$\endgroup$
  • $\begingroup$ @kocko one randomly chosen element $j$ with $A[j]>0$ is decreased with $x \in \{1 \dots A[j]\}$ $\endgroup$ – user8 Nov 24 '15 at 14:03
  • $\begingroup$ (If a comment seeks clarification, augment the question instead of commenting the comment.) I am confused about $j$ being an element, as well as an index into $A$ and $C$. What is $k$? If the number of counts (length of $C$) or $j$ was $O(k)$ and $j$ was known, where is the problem? $\endgroup$ – greybeard Nov 24 '15 at 16:38
1
$\begingroup$

How can I understand which element from A is reduced only by looking at C?

I guess you can make $C$ array two-dimensional $C[2][n]$ and in the second array you will initially (and after the counting step) store 0-es only. (This means when counting you will fill only the $C[0][n])

After, the counting step, your $C$ array should look like (taking the example above):

0 1 0 0 2  <- count of the elements with value i (i >= 0)
0 0 0 0 0  <- flag if the i-th element has been reduced.

When you reduce an element with value $j$, you will do:

  1. $C[0][j]$--; // decrease the count of $j$

  2. $C[0][j - x]++$; // increase the count of $(j - x)$

  3. $C[1][j]$ = 1; // set $j$ as decreased

This way, when you want to check if a value $j$ was reduced, you can just get the value of $C[1][j]$ and check if it is $1$. The complexity of this will be $O(1)$.

How can I sort it now in $O(k)$?

For the further sorting of the array, I don't think it's possible to do it in linear time (as Quicksort's complexity is $O(nlogn)$). You can, however, shift the decreased element to the left or to the right.

$\endgroup$
  • $\begingroup$ Given an array A, almost sorted with CountingSort, and an index $j$ where an element of A was reduced, how do you get A sorted in $O(k)$ time? $\endgroup$ – greybeard Nov 24 '15 at 15:00
  • $\begingroup$ I don't. The question is "How can I now sort the modified array in O(k)?" $\endgroup$ – Konstantin Yovkov Nov 24 '15 at 15:03
  • $\begingroup$ Given an array $A$, almost sorted with CountingSort, with the only exception that element of $A$ at a known index $j$ was reduced, how do you get $A$ sorted in $O(k)$ time, even with the counts still around? As in: what operations on $A$ take constant time, and how is their count bounded in growth by $O(k)$ with increasing $n$ - whatever $k$ may be? Or: How does knowing the modification index make this an $O(k)$ task? $\endgroup$ – greybeard Nov 24 '15 at 15:08
  • $\begingroup$ See my answer for an improvement. $\endgroup$ – Yuval Filmus Dec 27 '15 at 0:15
0
$\begingroup$

Here is an example. Suppose that the sorted array looks like this:

$$ 0000111222233444. $$

Now we reduce one of the $3$ entries to $1$. The new sorted array is

$$ 0000111122223444. $$

Let's put them side by side:

$$ 0000111222233444 \\ 0000111\mathbf{1}222\mathbf{2}3444 $$

The number of changes is bounded by the number of distinct elements (presumably, your $k$). Moreover, you can find the indices of the changes using your array $C$. This allows you to update the sorted array in time $O(k)$. I'm leaving the details to you.

$\endgroup$

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.