0
$\begingroup$

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.

$\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$
    – greybeard
    Apr 27, 2017 at 10:16
  • $\begingroup$ @greybeard understood your point $\endgroup$ Apr 27, 2017 at 12:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.