1

バブルソートを使用してアイテムが何回交換されたかを把握しようとしています。

Windowsに実装すると、問題なく動作します。しかし、g++ を使用して Linux に実装すると、出力がまったく異なり、バグを理解しようとして夢中になります。

ここに私のbubbleSort関数があります

int bubbleSort(string s){
int num = 0;

// Bubble sort string and count inversions on each swap
for (int i = 0; i < s.length(); i++) {
    for(int j = 0; j < s.length() - 1; j++) {
        if(s[j] > s[j+1]) {
            swap(s[j], s[j+1]);
            num++;
        }
    }
}
return num;
}

Windows と Linux の間で問題が発生している可能性があるこのコードに何か問題があると思われる人はいますか?

テスト入力: GCAD

6 を返す必要がありますが、G++ は 10 を返しています

4

2 に答える 2

3

コードを修正して、完全に機能するプログラムを作成しました。

#include <iostream>

int bubbleSort(std::string s) {
  int num = 0;
  for (int i = 0; i < s.length(); i++) {
    for(int j = 0; j < s.length() - 1; j++) {
      if(s[j] > s[j+1]) {
        std::swap(s[j], s[j+1]);
        num++;
        std::cout << "num is " << num << " and string is " << s << "\n";
      }
    }
  }
}

int main(void) {
  bubbleSort("ZWQM");
}

を使用して 64 ビット Linux マシンでコンパイルしましたg++。実行しました。結果：

num is 1 and string is WZQM
num is 2 and string is WQZM
num is 3 and string is WQMZ
num is 4 and string is QWMZ
num is 5 and string is QMWZ
num is 6 and string is MQWZ

6 回繰り返し、文字列を並べ替えます。この正確なプログラムがこの正確な出力を生成しないことを確認してください...そして、それが何をするか教えてください。

EDIT私は答えを得る方法を見つけました10! 文字列に改行文字を追加しました。

bubbleSort("ZWQM\n");

結果は

num is 1 and string is WZQM

num is 2 and string is WQZM

num is 3 and string is WQMZ

num is 4 and string is WQM
Z
num is 5 and string is QWM
Z
num is 6 and string is QMW
Z
num is 7 and string is QM
WZ
num is 8 and string is MQ
WZ
num is 9 and string is M
QWZ
num is 10 and string is
MQWZ

キャリッジ リターンが最初の文字位置に「バブルダウン」するため、出力がどのように混乱しているかに注意してください。あなたが観察した違いは、文字列をプログラムに取り込む方法に関連していること、および Windows と Linux では行末の扱いが異なることを 99% 確信しています。

于 2013-10-10T05:37:32.370 に答える
0

不要な比較を実行するには、ループ終了条件を次のように変更する必要があります。

for (int i = 0; i < s.length()-1; i++) {         
    for(int j = 0; j < s.length() - i - 1; j++) {
        if(s[j] > s[j+1]) {
            swap(s[j], s[j+1]);
            num++;
        }
    }
}

各反復の後、最後の要素が常にソートされます。

于 2013-10-10T05:14:01.490 に答える