Finding the loop invariant of selection sort

Question

I am trying to find then loop invariant of selection sort

Pseudo code

SELECTION SORT (A,n)
for i= 1 to n-1
    smallest=i
    for j=i+1 to n
        if A[j]<A[smallest]
                smallest=j
    exchange A[i] with A[smallest]

My answer for the loop invariant, is that the subarray A[1:i] is always sorted and consists of the smallest elements of A[1:n],however the official solution mentions that instead of A[1:i], it will be A[1:i-1].

Here's what I fail to understand, if the invariant is A[1:i-1],then when i=1 at initialization, we have A[1:0]. How does that make any sense? What does the subarray A[1:0] mean? Here's the link to the official solution

Answer 1

The misunderstanding probably stems from what the slice notation A[1:n] means. As is often the case with pseudo code, arrays start at position 1, and such slices are inclusive, i.e. the end position belongs to the sub array. This is unlike how it works in many programming languages where indexing starts at 0 and slices exclude the final index (e.g. in Python).

We can see that the author intended to include the ending position from this phrase in the referenced document:

the subarray A[1:─1] consists of the smallest ─1 elements

So, for example, in that notation A[1:1] is a sub array with one element (the first element), and thus A[1:0] denotes an empty sub array, which is indeed the initial situation when nothing is sorted yet.

Let's compare the two notations for an example array A = [10, 20, 30]

Pseudo code with 1-based positions and range ending after end position	Python code with 0-based indexes and range ending before end index	Slice result
A[1:3]	A[0:3]	[10, 20, 30]
A[1:2]	A[0:2]	[10, 20]
A[1:1]	A[0:1]	[10]
A[1:0]	A[0:0]	[]