bubble sort - Bubblesort: determining the invariant for inner- and outer-loop

Question

I am not 100 % sure how to determine the invariants for the following bubblesort-implementation:

BubbleSort(A[1,...,n])

s <- 1
while s = 1
        s <- 0
        for j <- 1 to length(A)
                if A[j] > A[j+1]
                        A[j] <-> A[j+1]
                        s <- 1

I would say the invariant for the inner-loop is: A[j] = max {A[k] | k in {1,..,j-1}}. However, I am not quite sure, whether I have to add the variable s to this particular invariant. If I have to I would say that (s = 0) => a_1 <= a_2 <= ... <= a_(j-1) is a good candidate. Is this correct? Or am I completely wrong?

Perhaps someone have a few minutes to help me. I would appreciate it.

question from:https://stackoverflow.com/questions/66068855/bubblesort-determining-the-invariant-for-inner-and-outer-loop

Answer 1

Waitting for answers