1
$\begingroup$

I am given the following invariant:

Invariant The greatest $i$ keys of an Array are always in sorted order on the last $i$ indices of the Array.

I am supposed to create a sorting Algortihm using this invariant. But I seem to have understood the concept of an Invariant differently, because with the information I find online, I can't find an idea for starting this problem. Do I have to create an algorithm that sorts the first $n-1$ elements in the array? Thanks for your help

$\endgroup$
  • $\begingroup$ How do you understand the concept of “invariant”? An invariant is a property that is supposed to hold for some thing. $\endgroup$ – Guildenstern Nov 7 '17 at 13:08
  • $\begingroup$ Yes, this is why I don't understand how I'm supposed to create an algorithm where something like that holds true at all times.. $\endgroup$ – chala Nov 7 '17 at 13:10
  • $\begingroup$ Don’t you understand the concepts of invariants in general, or this invariant in particular? I’ll invite you to ask about it in chat so that you can hash this out. ☺ $\endgroup$ – Guildenstern Nov 7 '17 at 13:12
  • $\begingroup$ At every step of your algorithm, the invariant should hold. I think you can use selection sort starting from the end. $\endgroup$ – klaus Nov 7 '17 at 16:56
1
$\begingroup$

Observations:

  1. For $i=0$, you don't know anything about the array.
  2. For $i=n$, the array is sorted.

So the idea is to go from $i=0$ to $n$ while maintaining the invariant. This is similar to an inductive proof; in fact, you'll get an inductive algorithm.

  • Start with the input array and $i=0$; clearly, the invariant is maintained.
  • For some $i \geq 0$, assume that the invariant holds. What do you do to ensure the invariant holds for $i+1$?

I'll let you take it from here.

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