0
$\begingroup$

The following is the definition for Proximate Sorting given in my paper:

An array of distinct integers is k-proximate if every integer of the array is at most k places away from its place in the array after being sorted, i.e., if the $i$th integer of the unsorted input array is the $j$th largest integer contained in the array, then $|i − j| ≤ k$.

The following is the proof for time complexity of k-proximate insertion sort:

To prove $O(nk)$, we show that each of the n insertion sort rounds swap an item left by at most $O(k)$.

In the original ordering, entries that are $≥ 2k$ slots apart must already be ordered correctly: indeed, if $A[s] > A[t]$ but $t − s ≥ 2k$, there is no way to reverse the order of these two items while moving each at most $k$ slots. This means that for each entry $A[i]$ in the original order, fewer than $2k$ of the items $A[0], . . . , A[i−1]$ are less than $A[i]$. Thus, on round $i$ of insertion sort when $A[i]$ is swapped into place, fewer than $2k$ swaps are required, so round $i$ requires $O(k)$ time.

My problem with the proof is this line : "This means that for each entry A[i] in the original order, fewer than 2k of the items $A[0], . . . , A[i−1]$ are less than A[i]". The preceding statements just proved that $t-s < 2k$, otherwise the elements are sorted (as elements with distance greater than $2k$ cannot be swapped.) Isn't the correct statement : "This means that for each entry A[i] in the original order, fewer than 2k of the items $A[0], . . . , A[i−1]$ are greater than A[i]"?

$\endgroup$
0
0
$\begingroup$

Yes if you sort the array in ascending order you are right it should be less than $2k$ elements in $A[0],...,A[i-1]$ are greater than $A[i]$. A simple array were the statement w is wrong ($k = 1$):

$$[1,2,3,4]$$

However is you sort in descending order it's the other way around. But you have a good point because this seems to imply that ascending is meant...

"indeed, if A[s] > A[t] but t − s ≥ 2k, there is no way to reverse the order of these two items"

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