英文:
Finding the loop invariant of selection sort
问题
The correct translation is:
我试图找到选择排序的循环不变式。
伪代码
选择排序（A，n）
对于 i=1 到 n-1
最小值=i
对于 j=i+1 到 n
如果 A[j]<A[最小值]
最小值=j
交换 A[i] 和 A[最小值]
关于循环不变式的问题，我的答案是子数组 A[1:i] 总是有序的，并且由 A[1:n] 中最小的元素组成，然而官方解答提到，应该是 A[1:i-1]。
我不明白的地方在于，如果循环不变式是 A[1:i-1]，那么在初始化时，当 i=1 时，我们得到 A[1:0]。这有什么意义呢？子数组 A[1:0] 是什么意思呢？
英文:
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
答案1
得分: 0
抱歉，代码部分不会被翻译。以下是翻译好的内容：
"这种误解可能源于 切片 表示法 A[1:n] 的含义。通常情况下，伪代码中数组从位置 1 开始，这样的切片是 包含 的，即结束位置属于子数组。这与许多编程语言中的工作方式不同，那些语言的索引从0开始，切片 不包括 最后一个索引（例如，在Python中）。
我们可以从引用文档中的这句话中看出作者的意图是 包括 结束位置：
子数组 A[1:𝑖─1] 由最小的 𝑖─1 个元素组成
因此，例如，在该表示法中 A[1:1] 是一个具有一个元素（第一个元素）的子数组，因此 A[1:0] 表示一个空的子数组，这确实是当尚未排序任何内容时的初始情况。
让我们比较一下对于一个示例数组 A = [10, 20, 30] 的这两种表示法：
| 使用1为基础位置和范围在结束位置之后的伪代码 | 使用0为基础索引和范围在结束索引之前的Python代码 | 切片结果 |
|---|---|---|
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] |
[] |
英文:
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<br>and range ending after end position | Python code with 0-based indexes<br>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] |
[] |
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论