C++ 中类似插入排序函数的行为不一致

问题描述 投票：0回答：2

我在 C++ 中遇到两个类似的插入排序函数的问题。这两个函数都旨在根据字符值按升序对字符串字符对向量进行排序。第一个函数 

insertionSort1
产生预期的排序输出，但第二个函数 
insertionSort2
（仅因递减操作 
j--
的位置不同）给出了意外且不正确的结果。

下面是演示两个排序函数及其各自输出的代码片段。这两个函数之间的唯一区别是，在 

insertionSort2
中，
j--
与赋值语句组合在一起，而在 
insertionSort1
中，它被分开到自己的行中。

#include <bits/stdc++.h>
using namespace std;

void insertionSort1(vector<pair<string,char>>&v) {
  for (int i=1; i<v.size(); i++) {
    auto curr=v[i];
    int j=i-1;
    while(j>=0 && curr.second<v[j].second) {v[j+1]=v[j]; v[j--];}
    v[j+1] = curr;
  }
}

void insertionSort2(vector<pair<string,char>>&v) {
  for (int i=1; i<v.size(); i++) {
    auto curr=v[i];
    int j=i-1;
    while(j>=0 && curr.second<v[j].second) {v[j+1]=v[j--];}
    v[j+1] = curr;
  }
}

int main() {
  vector<pair<string, char>> v1 {
    {"Alice"  , 'B'},
    {"Bob"    , 'A'},
    {"Charlie", 'B'},
    {"David"  , 'A'}
  };
  // Print the original vector
  for(auto i : v1) cout << "{" << i.first << ", " << i.second << "} "; cout << endl; // {Alice, B} {Bob, A} {Charlie, B} {David, A}
  // Sort the vector
  insertionSort1(v1);
  // Print the sorted vector
  for(auto i : v1) cout << "{" << i.first << ", " << i.second << "} "; cout << endl; // {Bob, A} {David, A} {Alice, B} {Charlie, B}
  
  cout << "///////////////////////////////////////////\n";
  
  vector<pair<string, char>> v2 {
    {"Alice"  , 'B'},
    {"Bob"    , 'A'},
    {"Charlie", 'B'},
    {"David"  , 'A'}
  };
  // Print the original vector
  for(auto i : v2) cout << "{" << i.first << ", " << i.second << "} "; cout << endl; // {Alice, B} {Bob, A} {Charlie, B} {David, A}
  // Sort the vector
  insertionSort2(v2);
  // Print the sorted vector
  for(auto i : v2) cout << "{" << i.first << ", " << i.second << "} "; cout << endl; // {Bob, A} {Bob, A} {David, A} {David, A} // Unexpected output occurs here!
  return 0;
}

两个向量的预期排序输出应该是：

{Bob, A} {David, A} {Alice, B} {Charlie, B}

但是，使用insertionSort2后得到的实际输出是不正确的：

{Bob, A} {Bob, A} {David, A} {David, A}

为什么 insertSort2 会产生不正确的结果，而它看起来与 insertSort1 之间只有细微的语法差异，而按预期工作？

c++ algorithm sorting vector insertion-sort
2个回答
0
投票

在 C++17 及更高版本中，保证在对左侧进行任何评估之前完全评估赋值表达式的右侧，包括所有副作用。请参阅：Gabriel Dos Reis、Herb Sutter 和 Jonathan Caves 的精炼惯用 C++ 的表达式求值顺序。

然后考虑第一个作业（即向右移动），当：

  • i
    ==1
  • j
    ==0
  • j + 1
    ==1

您希望将 v[0] 复制到 v[1]，使用表达式 

v[j + 1] = v[j--];

然而，在计算 

j
之前，
j + 1
会被递减。

  • j
    的原始值== 0
  • j
    的递减值 == -1
  • j
    的递减值 + 1 == 0

因此，不是将 v[0] 复制到 v[1]，而是将其复制回 v[0]。

所以事情并没有朝着他们应该去的方向发展。最终，这会导致数据被扰乱，如您所见。

输出运算符/调试例程

我添加了以下输出运算符，因此我可以观看排序步骤。

// main.cpp

//#include <bits/stdc++.h>
#include <iomanip>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using std::cout;
using std::pair;
using std::string;
using std::vector;

using namespace std;

std::ostream& operator<< (std::ostream& ost, std::pair<std::string, char> const& p)
{
    ost << '{' << std::quoted(p.first) << ",'" << p.second << "'}";
    return ost;
}

std::ostream& operator<< (std::ostream& ost, vector<pair<string, char>> const& v)
{
    ost.put('[');
    if (!v.empty())
    {
        auto n_commas{ v.size() - 1u };
        for (std::size_t i{}; i < n_commas; ++i)
            ost << v[i] << ',';
        ost << v.back();
    }
    ost.put(']');
    return ost;
}

void debug(
    std::string const& heading, 
    int const i, 
    int const j, 
    std::vector<std::pair<std::string, char>>& v)
{
    std::cout << heading << ": " 
        << "i: " << i
        << ", j: " << j
        << ", v: "<< v 
        << '\n';
}

void insertionSort1(vector<pair<string, char>>& v) {
    for (int i = 1; i < v.size(); i++) {
        auto curr = v[i];
        int j = i - 1;
        debug("is1, before loop j", i, j, v);
        while (j >= 0 && curr.second < v[j].second) { v[j + 1] = v[j]; v[j--]; }
        v[j + 1] = curr;
    }
}

void insertionSort2(vector<pair<string, char>>& v) {
    for (int i = 1; i < v.size(); i++) {
        auto curr = v[i];
        int j = i - 1;
        debug("is2, before loop j", i, j, v);
        while (j >= 0 && curr.second < v[j].second) { v[j + 1] = v[j--]; }
        v[j + 1] = curr;
    }
}

int main() {
    vector<pair<string, char>> v1{
      {"Alice"  , 'B'},
      {"Bob"    , 'A'},
      {"Charlie", 'B'},
      {"David"  , 'A'}
    };
    // Print the original vector
    for (auto i : v1) cout << "{" << i.first << ", " << i.second << "} "; cout << endl; // {Alice, B} {Bob, A} {Charlie, B} {David, A}
    // Sort the vector
    insertionSort1(v1);
    // Print the sorted vector
    for (auto i : v1) cout << "{" << i.first << ", " << i.second << "} "; cout << endl; // {Bob, A} {David, A} {Alice, B} {Charlie, B}

    cout << "///////////////////////////////////////////\n";

    vector<pair<string, char>> v2{
      {"Alice"  , 'B'},
      {"Bob"    , 'A'},
      {"Charlie", 'B'},
      {"David"  , 'A'}
    };
    // Print the original vector
    for (auto i : v2) cout << "{" << i.first << ", " << i.second << "} "; cout << endl; // {Alice, B} {Bob, A} {Charlie, B} {David, A}
    // Sort the vector
    insertionSort2(v2);
    // Print the sorted vector
    for (auto i : v2) cout << "{" << i.first << ", " << i.second << "} "; cout << endl; // {Bob, A} {Bob, A} {David, A} {David, A} // Unexpected output occurs here!
    return 0;
}
// end file: main.cpp

输出

{Alice, B} {Bob, A} {Charlie, B} {David, A}
is1, before loop j: i: 1, j: 0, v: [{"Alice",'B'},{"Bob",'A'},{"Charlie",'B'},{"David",'A'}]
is1, before loop j: i: 2, j: 1, v: [{"Bob",'A'},{"Alice",'B'},{"Charlie",'B'},{"David",'A'}]
is1, before loop j: i: 3, j: 2, v: [{"Bob",'A'},{"Alice",'B'},{"Charlie",'B'},{"David",'A'}]
{Bob, A} {David, A} {Alice, B} {Charlie, B}
///////////////////////////////////////////
{Alice, B} {Bob, A} {Charlie, B} {David, A}
is2, before loop j: i: 1, j: 0, v: [{"Alice",'B'},{"Bob",'A'},{"Charlie",'B'},{"David",'A'}]
is2, before loop j: i: 2, j: 1, v: [{"Bob",'A'},{"Bob",'A'},{"Charlie",'B'},{"David",'A'}]
is2, before loop j: i: 3, j: 2, v: [{"Bob",'A'},{"Bob",'A'},{"Charlie",'B'},{"David",'A'}]
{Bob, A} {Bob, A} {David, A} {David, A}

整数呢？

@Taher Anaya，OP，报告该问题仅在对对排序时发生，具体来说，在对整数排序时不会发生。对此我没有任何解释。上面的分析表明它应该影响使用 

insertionSort2
排序的任何对象。

如果可以的话，Taher，请发布一个程序来证明整数数据没有问题。

0
投票

@tbx免费软件 

If possible, Taher, please post a program that demonstrates that there is no problem with integer data.

#include <bits/stdc++.h>
using namespace std;

void insertionSort1(vector<int>&v) {
  for (int i=1; i<v.size(); i++) {
    auto curr=v[i];
    int j=i-1;
    while(j>=0 && curr<v[j]) {v[j+1]=v[j]; v[j--];}
    v[j+1] = curr;
  }
}

void insertionSort2(vector<int>&v) {
  for (int i=1; i<v.size(); i++) {
    auto curr=v[i];
    int j=i-1;
    while(j>=0 && curr<v[j]) {v[j+1]=v[j--];}
    v[j+1] = curr;
  }
}

int main() {
  vector<int> v1 {7, 4, 1, 2, 3, 6, 9, 8, 5};
  for(auto i : v1) cout << i << " "; cout << endl; // 7 4 1 2 3 6 9 8 5
  insertionSort1(v1);
  for(auto i : v1) cout << i << " "; cout << endl; // 1 2 3 4 5 6 7 8 9
  
  cout << "//////////////////\n";
  
  vector<int> v2 {7, 4, 1, 2, 3, 6, 9, 8, 5};
  for(auto i : v2) cout << i << " "; cout << endl; // 7 4 1 2 3 6 9 8 5
  insertionSort2(v2);
  for(auto i : v2) cout << i << " "; cout << endl; // 1 2 3 4 5 6 7 8 9
  return 0;
}```
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.