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$ 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 '17 at 10:16
  • $\begingroup$ @greybeard understood your point $\endgroup$ – Shubham Singh rawat Apr 27 '17 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.