3

クイックソート、挿入ソート、マージソートを実装するプログラムを書いています。マージソート以外はすべて機能しますが、その理由がわかりません。操作変数と比較変数は無視してください。それらは、さまざまな入力ファイルの実行時間と操作数を分析できるようにするためです。このコードは、次の方法でクラス オブジェクトを介してメインから実行されます。

Merge testobj13(test_Med[0], 100);
    testobj13.merCall();
    testobj13.display();

ソートされたリストの場合、クラスはリストをソートしたままにします。反転したリストの場合、リストは最初と最後の値を除いてほとんど反転したままです。ランダム化されたリストの場合、出力と元の入力の間にパターンは見られません。回答を待っている間、他の質問に回答しようとします。ここでの全体的な問題に関係のない私のコードまたは構文に関するものであっても、批判は大歓迎です。このコードは、アルゴリズム クラスによって作成された sudo コードに基づいて作成したため、ここで何が問題なのかを見つけるのに苦労しています。

# include <iostream>
# include <stdio.h>
# include <stdlib.h>

using namespace std;
class Merge{
public:
    int comparisons, operations, middle, i, j, k, size;
    int *myArray, *c;

Merge::~Merge(){
    myArray = 0;
    delete myArray; 
}

Merge::Merge(int a [], int n) {
    size= n;
    myArray= new int[size];
    comparisons = 0, operations = 0, middle = 0, i = 0, j = 0, k = 0;

    for(int x = 0; x < size; x++){
       myArray[x] = a[x];
    }
}

void combine(int arr [], int first, int middle, int last){

i = first, j = middle + 1, k = first; operations = operations + 3;
c = new int[last + 1]; operations ++;

while( (i <= middle) && (j <= last) ){
    comparisons++;operations++;
    if(arr[i] <= arr[j]){operations++;
        c[k] = arr[i]; operations++;
        i++; operations++;
    }
    else{
        c[k] = arr[j]; operations++;
        j++; operations++;
    }
    k++; operations++;
}
while(i <= middle){operations++;
    c[k] = arr[i]; operations++;
    i++; operations++;
    k++; operations++;
}
while(j <= last){operations++;
    c[k] = arr[j]; operations++;
    j++; operations++;
    k++; operations++;
}
for(int k = first; k <= last; k++){operations++;
    arr[k] = c[k]; operations++;
}
c = 0;
delete c;
}

void mer(int arr [], int first, int last){
operations++; //for the comparison in the following if statement
if ( first < last ){
    middle = (first + last) / 2; operations++;
    mer(arr, first, middle);  operations++;
    mer(arr, middle + 1, last); operations++;
    combine(arr, first, middle, last); operations++;
}
}

void merCall(){
mer(myArray, 0, size - 1);
}

void display(){

cout << "The array after going through Merge Sort: " ;

for(int x = 0; x < size; x++){
    cout << endl << myArray[x];
}

cout << endl << "Number of operations :" << operations << "\t comparisons: " <<   comparisons << endl;

}


};
4

1 に答える 1

1

「中間」変数は、ローカル変数ではなくクラスメンバーであるため、再帰中に上書きされます。

middle = (first + last) / 2; operations++;

// This is going to affect middle
mer(arr, first, middle);  operations++;

// So this isn't going to work on the range you think it is.
mer(arr, middle + 1, last); operations++;

combine(arr, first, middle, last); operations++;

Middleをローカル変数として宣言することをお勧めします。

int middle = (first + last) / 2; operations++;
mer(arr, first, middle);  operations++;
mer(arr, middle + 1, last); operations++;
combine(arr, first, middle, last); operations++;
于 2012-11-04T20:29:29.707 に答える