1. for j = 1..i-1, we're trying to "insert" a[i] into a[1..i-1]. Try simulating it yourself. I believe you will find out it's insertion sort.
2. for j = i..n, we're replacing a[i] with the smallest element among a[i..n].
Why it works: either (1) or (2) alone CAN DO THE SORTING. They do not conflict with each other.
Therefore, we can "optimize" this algorithm in at least two ways.
BTW, hope future powerful compilers can do this :)
> Letme re-interpret what the i-th iteration of the algorithm does:
> 1. for j = 1..i-1, we're trying to "insert" a[i] into a[1..i-1]. Try simulating it yourself. I believe you will find out it's insertion sort.
> 2. for j = i..n, we're replacing a[i] with the smallest element among a[i..n].
That is, they're saying in (2) that after an iteration of the outer loop, the ith value will be the smallest of all the values that succeed it in the sequence. This is demonstrably false. It is always the maximum value of the sequence itself, regardless of its initial position relative to i.
The following Python code is used to print out the result of running the inner loop on an arbitrary sequence but without altering the original value (so it won't actually be sorted at the end). The point is to demonstrate that the maximum value always ends in the ith position:
def inner(a, i):
for j in range(len(a)):
if a[i] < a[j]:
a[i], a[j] = a[j], a[i]
print(a)
def outer(a):
for i in range(len(a)):
inner(a.copy(), i)
a = [5,4,3,2,1,6]
outer(a)
[6, 4, 3, 2, 1, 5]
[4, 6, 3, 2, 1, 5]
[3, 4, 6, 2, 1, 5]
[2, 4, 3, 6, 1, 5]
[1, 4, 3, 2, 6, 5]
[5, 4, 3, 2, 1, 6]
[6, 4, 3, 2, 1, 5]
[4, 6, 3, 2, 1, 5]
[3, 4, 6, 2, 1, 5]
[2, 3, 4, 6, 1, 5]
[1, 2, 3, 4, 6, 5]
[1, 2, 3, 4, 5, 6]
[5, 4, 3, 2, 1, 6]
[4, 5, 3, 2, 1, 6]
[3, 4, 5, 2, 1, 6]
[2, 3, 4, 5, 1, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]