3 ms·

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.

by limoce 5y ago

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]. 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 :)

kilovoltaire 5y ago
I think you misread the code, the comparison is the opposite of what you might expect, so a[i] is always the largest element, and it is not inserted into a[1..i-1]
- edflsafoiewq 5y ago
  No, GP is correct. At the beginning of an outer loop iteration, a[1..i-1] is sorted with a[i-1] the maximum element. The inner loop inserts a[i] into a[1..i-1] so that at the end of the iteration, a[1..i] is sorted with a[i] the max.
  - Jtsummers 5y ago
    No, GGP is incorrect. To be clear, they wrote: > 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] Note that 6 ends up in the ith position after finishing the inner loop. If we let it sort (so remove .copy()), after each iteration the maximum value is, again, always at the ith position: [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] GGP is correct that it's basically insertion sort otherwise, (1). To illustrate, the behavior if you don't compare every pair is the same as insertion sort: [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] This is done by stopping the inner loop once j reaches i.
    - edflsafoiewq 5y ago
      Yeah, you're right, (2) is wrong. (1) is correct.

by limoce 5y ago

kilovoltaire 5y ago

I think you misread the code, the comparison is the opposite of what you might expect, so a[i] is always the largest element, and it is not inserted into a[1..i-1]

edflsafoiewq 5y ago
No, GP is correct. At the beginning of an outer loop iteration, a[1..i-1] is sorted with a[i-1] the maximum element. The inner loop inserts a[i] into a[1..i-1] so that at the end of the iteration, a[1..i] is sorted with a[i] the max.
- Jtsummers 5y ago
  No, GGP is incorrect. To be clear, they wrote: > 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] Note that 6 ends up in the ith position after finishing the inner loop. If we let it sort (so remove .copy()), after each iteration the maximum value is, again, always at the ith position: [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] GGP is correct that it's basically insertion sort otherwise, (1). To illustrate, the behavior if you don't compare every pair is the same as insertion sort: [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] This is done by stopping the inner loop once j reaches i.
  - edflsafoiewq 5y ago
    Yeah, you're right, (2) is wrong. (1) is correct.