2

この C# コードを次のように C++に変換しました。

void bubbleSort(int *inputArray, int passStartIndex, int currentIndex,int length)
{
    if(passStartIndex == length - 1) return;
    if(currentIndex == length - 1) return bubbleSort(inputArray, passStartIndex+1, passStartIndex+1,length);

    //compare items at current index and current index + 1 and swap if required
    int nextIndex = currentIndex + 1;
    if(inputArray[currentIndex]>inputArray[nextIndex])
    {
        int temp = inputArray[nextIndex];
        inputArray[nextIndex] = inputArray[currentIndex];
        inputArray[currentIndex] = temp;
    }

    return bubbleSort(inputArray, passStartIndex, currentIndex + 1,length);
}

しかし、長さ50100の入力配列で実行すると、expcetionが表示されます

System.StackOverflowException は処理されませんでした メッセージ: タイプ 'System.StackOverflowException' の未処理の例外が example.exe で発生しました

私は何を間違っていますか？修正方法は？

4

2 に答える 2

3

問題は解決しませんが (再帰制限を参照)、使用したアルゴリズムに誤りがあります。交換する必要があります

if (currentIndex == length - 1)
    return bubbleSort(inputArray, passStartIndex+1, passStartIndex+1, length);

に

if (currentIndex == length - 1)
    return bubbleSort(inputArray, passStartIndex+1, 0,length - 1);

最初の項目は適切な場所にありませんが、最後の項目は適切な場所にあるため、バブル ソートは 0 から再開する必要があります。

于 2013-02-12T19:14:07.953 に答える
3

「私は何を間違っていますか？」

再帰関数が自分自身を呼び出すたびに、呼び出しフレーム (アクティベーション レコード) がスタック メモリに格納されます。したがって、再帰が深くなりすぎると、スタックの最大サイズに達する瞬間に実行が終了します。

こちらもご覧ください: C++ は再帰の深さを制限しますか?

「どうやって直すの？」

この問題を回避する最も簡単な方法は、最初からアルゴリズムを再帰として設計しないことです。しかし、このような再帰的な解決策があれば、ほとんどの場合、それをループ形式または (通常ははるかに簡単です)末尾再帰に書き直すことができます。

基本的に、次の呼び出しに引数を直接渡さないように関数を書き直すことができれば、勝ったことになります。currentIndex再帰を見ると、自分自身を呼び出す場所と呼び出しが行われる前の 2 つの場所があり、passStartIndex変更されています。これらのインデックスを別の場所に保存し、現在の関数呼び出しが「完了しました。これらは誰かが続行する必要がある値です: ... これで続行できます!」というシグナルを送るだけだと想像してください。、つまり、関数の状態を保存する必要はありません。そうすることで、 Tail 呼び出しが終了します(特に最初のサンプル プログラムを参照してください)。

コードでそれを行う方法の完全な例を次に示します:ステップ 1、ステップ 2

于 2013-02-12T19:00:40.227 に答える