时间戳

首页 > 解决方案 > 高级选择排序 - 在一次迭代中搜索两个元素

c++ - 高级选择排序 - 在一次迭代中搜索两个元素

问题描述

我有一个作业，我必须使用以下参数“改进”SelectionSort：

好的，到目前为止我写了这个 c++ 代码：

    #include <iostream>
    #include <array>
    #include <string>

    using namespace std;

    int main()
    {
    int min, min2;

    // doesn't work
    array<int, 9> list = { 97,34,15,25,27,4,19,41,68 };

    /* this one works:
    array<int, 10> list = { 4,8,1,3,10,6,5,7,9,2 }; 
    */

    // First loop
    for (int i = 0; i < list.size(); i+=2) {
        min = i;
        min2 = i + 1;

        // 2nd Loop for searching the smallest elements
        for (int j = i + 2; j < list.size(); j++) {

            if (list.at(j) < list.at(min)) {
                min = j;
            }

            // outer if -> stop before out of array
            if (j+1 < list.size()) {
                if (list.at(j+1) < list.at(min2)) {
                    min2 = j+1;
                }
            }   
        }
        swap(list.at(i), list.at(min));
        // Prevent out of array error
        if (i + 1 < list.size()) {
            swap(list.at(i+1), list.at(min2));
        }
    }

    cout << '\n' << '\n';
    cout << "Sorted list: " << endl;
    for (int elem : list) {
        cout << elem << ", ";
    }
  }

当然是排序，这就是结果……但不是我希望的结果：

4, 97, 15, 19, 25, 34, 27, 41, 68,

我没有想法，我得到的唯一提示是：“没有第三个循环”。

我将不胜感激任何帮助 ：-）

编辑：

由于投票保持不变，我尝试指定问题。当我使用高 int 值（例如代码中的值）时，排序算法无法正常工作

如您所见，第一个 if 语句中位置 0、2、4、6、8 上的值已正确排序，但其他值则没有形成第二个 if 语句。

例如，当我将 int 值更改为 1-10 的值并将它们随机混合时，算法似乎工作正常（感谢您的评论！）：

我没有想法 - 是编程错误还是算法错误？

编辑 3： 这是我的（最终工作的）更新代码：

//array<int, 10> list = { 4,8,1,3,10,6,5,7,9,2 };
//array<int, 4> list = { 97,15,25,18 };
//array<int, 2> list = { 97,18 };
array<int, 3> list = { 4,5,3 };

// First loop
for (int i = 0; i < list.size(); i+=2) {
    if (i == list.size() - 1) {
        break;
    }
    min = i;
    min2 = i + 1;

    // Enforce that list.at(min) <= list.at(min2) -> Sorting pivot (element) for the algorithm to smallest, 2nd smallest.
    if (list.at(min) > list.at(min2)) {
        swap(list.at(min), list.at(min2));
    }

    // Second Loop
    for (int j = i + 2; j < list.size(); ++j) {
        if (list.at(j) < list.at(min)) {
            min2 = min; // min2 points now on the 2nd smallest element
            min = j; // min points now on the smallest element
        }
        else if (list.at(j) < list.at(min2)) {
            min2 = j;
        }
    }

    // Swapping the elements in the right position.
    swap(list.at(i + 1), list.at(min2));
    swap(list.at(i), list.at(min));
}

结果：

{ 4,8,1,3,10,6,5,7,9,2 } -> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

{ 97,15,25,18 } -> 15, 18, 25, 97,

{ 97,18 } -> 18, 97,

{ 4,5,3 } -> 3, 4, 5,

标签： c++algorithmselection-sort

解决方案

用数组试试你的程序[97,18]。我想你会发现它不起作用，因为永远不会进入第二个循环，并且第一个循环末尾的行不会交换任何内容。

当我在评论中说min必须小于或等于时min2，我的意思是说您必须确保list.at(min) <= list.at(min2)。我上面的 2 项数组示例说明了为什么这很重要。

强制执行的方法是修改您的第一个循环：

// First loop
for (int i = 0; i < list.size(); i+=2) {
    if (i == list.size()-1) {
        // There is an odd number of items in the list.
        // At this point, we know that the last item is in place.
        // So just exit.
        break;
    }
    min = i;
    min2 = i + 1;

    // enforce list(min) <= list(min2)
    if (list.at(min) > list.at(min2)) {
        swap(list.at(min), list.at(min2));
    }

    // second loop

而且，是的，您必须在内部循环中维护它。如果您尝试使用数组[4,5,3]，结果将是[3,5,4].

这主要是因为在您的内部循环中，当您找到 时list.at(j) < list.at(min)，您会交换项目。但是什么时候list.at(min2) > list.at(min)，你所做的就是乱序交换东西。

您应该使用该 3 元素列表在调试器中单步执行您的代码，以了解正在发生的事情。如果您不知道如何使用调试器，请立即停下来学习。当您可以查看代码的逐行执行时，很容易发现这种类型的编程错误。另一种方法是手工完成：用一张纸和铅笔，一步一步地浏览代码，写下每个变量的变化。

您的内部循环的另一个问题是您正在检查list.at(j+1). list.at(min2)但是你j每次只增加 1，所以你最终会做额外的工作。没有理由做额外的检查。它将在下一次循环中处理。

假设您保持 和 之间的正确关系，则内部循环中的修复min很min2容易。如果list.at(j) < list.at(min)，则设置min2=min（因为min现在指向第二小的项目），然后设置min=j。如果list.at(j) < list.at(min2)，则只需设置min2=j。代码如下所示：

for (j = i+2; j < list.size(); ++j) {
    if (list.at(j) < list.at(min)) {
        min2 = min;
        min = j;
    } else if (list.at(j) < list.at(min2)) {
        min2 = j;
    }
}

现在，您在外循环末尾的代码可以正常工作。

调试

使用数组在调试器中运行您的程序[4,5,3]。在内循环之后的行上放置一个断点，这里：

    swap(list.at(i), list.at(min));

如果您检查该数组，您会发现它仍然是[4,5,3]. 但是看看min和min2。你会看到min=2和min2=0。i等于0。现在，当您在list[i]和处交换项目时会发生什么list[min]？你得到[3,5,4]，并且min2不再指向第二小的项目。

有几种不同的情况会发生这种情况。您必须考虑这些条件并处理它们。我提供的代码可以让你找到最小的和第二小的项目。但是您必须弄清楚在找到它们之后如何将它们交换到正确的位置。

推荐阅读