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

Advanced SelectionSort - Search two elements in one iteration

我有一个家庭作业，我必须 "improve" 使用以下参数进行选择排序：

好的，到目前为止我写了这个 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,

我没有想法，我得到的唯一提示是："no third loop"。

如有任何帮助，我将不胜感激:-)

编辑：

由于投票暂缓，我尝试详细说明问题。 当我使用高 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,

Try your program with the array [97,18]. I think you'll find that it doesn't work, because the 2nd loop is never entered, and the lines at the end of the first loop won't swap anything.

When I said in my comment that min must be less than or equal to min2, I meant to say that you must ensure list.at(min) <= list.at(min2). My example above of the 2-item array shows why that's important.

The way to enforce that is to modify your first loop:

// 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

And, yes, you must maintain that in the inner loop. If you try with the array [4,5,3], the result will be [3,5,4].

That's primarily because in your inner loop, when you find that list.at(j) < list.at(min), you swap the items. But when list.at(min2) > list.at(min), what you've done is swap things out of order.

You should single-step your code in the debugger using that 3-element list to understand what's happening. If you don't know how to use the debugger, stop right now and learn. This type of programming error is very easy to discover when you can watch a line-by-line execution of your code. The alternative is to do it by hand: with a piece of paper and pencil, walk through the code step by step, writing down the change to every variable.

The other problem with your inner loop is that you're checking list.at(j+1) with list.at(min2). But you're only incrementing j by 1 each time, so you end up doing extra work. There's no reason to do that extra check. It'll be handled the next time through the loop.

The fix in the inner loop, assuming that you maintain the proper relationship between min and min2, is easy enough. If list.at(j) < list.at(min), then set min2=min (because min is now pointing to the second-smallest item), and set min=j. If list.at(j) < list.at(min2), then just set min2=j. The code looks like this:

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;
    }
}

Now your code at the end of the outer loop works correctly.

Debugging

运行 your program in the debugger with the array [4,5,3]. Place a breakpoint on the line just after the inner loop, here:

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

If you examine the array, you'll see that it's still [4,5,3]. But look at min and min2. You'll see that min=2 and min2=0. i is equal to 0. Now, what happens when when you swap the items at list[i] and list[min]? You get [3,5,4], and min2 no longer points to the second smallest item.

There are several different conditions in which something like this can happen. You have to think of those conditions, and handle them. The code I provided lets you find the smallest and 2nd smallest items. But you have to figure out how to swap things into the correct places after you've found them.