3 ms·
Isn't the proof incomplete because it does not ensure that the result is a permutation of the original array contents? Just overwriting the entire array with it
by fweimer 4y ago
Isn't the proof incomplete because it does not ensure that the result is a permutation of the original array contents? Just overwriting the entire array with its first element should still satisfy the post-condition as specified, but is obviously not a valid sorting implementation.
- touisteur 4y agoIt was touched upon in the post: 'Tip: Don’t prove what you don’t need to prove' (and surrounding text). With a link on another proof for another sorting algorithm.
- yannickmoy 4y agoand there are actually multiple ways to prove that the result is a permutation of the entry, either by computing a model multiset (a.k.a. bag) of the value on entry and exit and showing they are equal, or by exhibiting the permutation to apply to the entry value to get the exit value (typically by building this permutation as the algorithm swaps value, in ghost code), etc. but none of this makes a good read for people not already familiar with program proof tools.