c++ - Advanced SelectionSort - 在一次迭代中搜索两个元素

Question

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

• 使用“改进的”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 值(例如代码中的值)时，排序算法无法正常工作

• 列表:array<int, 9> list = { 97,34,15,25,27,4,19,41,68 };
• 结果:4, 97, 15, 19, 25, 34, 27, 41, 68,

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

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

• 列表:array<int, 10> list = { 4,8,1,3,10,6,5,7,9,2 };
• 结果:1, 2, 4, 3, 5, 6, 8, 7, 9, 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,

Answer 1

用数组 [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不再指向第二小的项目。

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