英文:
Why does this code generates unexpected output?
问题
vector<int> arr = {11, 10, 13, 12, 19, 14};
for (int i = 0; i < arr.size() - 1; i++) {
int min = arr[i];
for (int j = i + 1; j < arr.size(); j++) {
if (arr[j] < min)
// min=j;
swap(min, arr[j]);
}
// cout<<min<<" ";
}
我知道正确的选择排序算法，但我不知道这段代码实际上是如何工作的。
英文:
vector<int> arr = {11, 10, 13, 12, 19, 14};
for (int i = 0; i < arr.size() - 1; i++) {
int min = arr[i];
for (int j = i + 1; j < arr.size(); j++) {
if (arr[j] < min)
// min=j;
swap(min, arr[j]);
}
// cout<<min<<" ";
}
I know the correct selection sort algorithm but i don't know how this code is actually working
答案1
得分: 5
swap(min, arr[j]); 交换了错误的东西，因为 min 是 arr[i] 的 副本。
如果要交换 arr[i] 和 arr[j]，你需要将 min 设为 arr[i] 的 引用：
for (std::size_t i = 0; i + 1 < arr.size(); i++) {
int& min = arr[i]; // <- 注意 `int&`
for (std::size_t j = i + 1; j < arr.size(); j++) {
if (arr[j] < min) {
std::swap(min, arr[j]);
}
}
}
// 在冒泡排序完成后最好再打印，你代码中打印 `min` 的注释有点令人困惑。
注意：在代码中打印 min 的注释有点令人困惑。最好在冒泡排序完成后再进行打印。
英文:
swap(min, arr[j]); will swap the wrong thing since min is a copy of arr[i].
If you want it to swap(arr[i], arr[j]); you need to make min a reference to arr[i]:
for (std::size_t i = 0; i + 1 < arr.size(); i++) {
int& min = arr[i]; // <- note `int&`
for (std::size_t j = i + 1; j < arr.size(); j++) {
if (arr[j] < min) {
std::swap(min, arr[j]);
}
}
}
//for(int val : arr) std::cout << val << ' ';
Note: Your comment in the code printing min is confusing. Printing should preferably be done after the bubblesorting is done.
答案2
得分: 0
你之所以得到意外的输出，是因为你的代码缺少在未排序子列表（嵌套循环）中找到的最小元素与最左边的未排序元素arr[i]进行交换。
只需在嵌套循环之后添加以下代码（在你注释掉打印min的地方），你将会得到预期的输出：
if (min != arr[i]) {
arr[i] = min;
}
也就是说，这是一种实现选择排序的低效方式，因为你的嵌套循环可能会导致多次元素交换。最好在内部循环中跟踪最小元素的索引在min中（在进入嵌套循环之前，min应该保存索引i而不是在i索引处的值），然后在嵌套循环之后，如果a[i]和a[min]不同，就交换a[min]和a[i]。
英文:
You are getting unexpected output because your code is missing the exchange (swap) of smallest element found in unsorted sublist (nested loop) with the left most unsorted element, which is arr[i].
Just add following code after nested loop (at the place where you commented out printing min) and you will get the expected output
if (min != arr[i]) {
arr[i] = min;
}
That said, this is inefficient way of implementing selection sort because your nested loop may end up swapping of elements multiple times. Better to keep track of index of smallest element in inner loop in min (min should hold index i instead of value at i<sup>th</sup> index before entering nested loop) and, after nested loop, swap a[min] with the a[i] if a[i] and a[min] are different.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论