By the statement of the question i am trying to generalize the structure of the array.for me Being at their correct position means they can't be shifted. I tried to come up with a few examples and deducted such an array has to be 2-sorted or all the sorted elements are in the first half. for a k-sorted array we can use insertion sort or heap sort with a heap of size k, but first i need to make some generalization about the structure of the array. How do we go about proving it formally? Intuitive explanation would work too.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Is a predicate available telling mobile index/element from immobile? Just initialise another array with the indices of mobile elements and sort using another level of indirection. $\endgroup$– greybeardApr 27, 2017 at 10:16
-
$\begingroup$ @greybeard understood your point $\endgroup$– Shubham Singh rawatApr 27, 2017 at 12:24
Add a comment
|