0

私は挿入/マージソートプログラムを作成しようとしていますが、両方を行い、最大 1,000 万のシリーズの長い配列の入力を受け入れる必要があります。マージソートの場合、ソートには数秒かかりますが、私の友人によると、挿入には6時間以上かかるはずです。プログラムにタイマーを入れて、30分間作業した後に停止させたいのですが、どうにかして並べ替えを完了できませんが、どのように、またはどこに置くかわかりません。

タイマーを必要とする唯一のものであるため、メインメソッドと挿入ソートのコードを次に示します。誰が何をすべきか、どこから始めるべきか知っていますか?

void insertionSort(int arr[], int length) {
    int i, j, tmp;
    for (i = 1; i < length; i++) {
        j = i;
        while (j > 0 && arr[j - 1] > arr[j]) {
            tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
            j--;
        }
    }
}

int main()
{
    srand (time(0));

    long x;

    cout << "how long will the array be?\n" <<
    "10, 100, 1000, 10000, 100000, 1000000, or 10000000?" << endl;
    cin >> x;

    switch(x){

        case 10:
            x = 10;
            break;

        case 100:
            x = 100;
            break;

        case 1000:
            x = 1000;
            break;

        case 10000:
            x = 10000;
            break;

        case 100000:
            x = 100000;
            break;

        case 1000000:
            x = 1000000;
            break;

        case 10000000:
            x = 10000000;
            break;

        default:
            cout << "Error, incorrect number entered, please try again!" << endl;


    }

    static int ar[10000000];

    for(int i = 0; i < x; i++){

        ar[i] = rand() % 100000001;
    }


    int c= 0;
    cout << "which sorting method would you like to use?\n" <<
    "Insertion(1), merge(2), or quick(3)? \nPlease enter the number beside the one you want to use" << endl;
    cin >> c;

    if(c == 1){
        insertionSort(ar, x);

    }
    else if(c==2){
        for (int i = 1; i < x; i *= 2) {
            for (int j = 0; j < x- i; j += 2*i) {
                int iEnd2 = (2*i < x - j) ? 2*i : x - j;
                Merge(&(ar[j]), i, iEnd2);
            }
        }


    }    else if(c==3){
        quickSort(ar,0,x-1);

    }    else{

        cout << "You did not enter a correct number, please try again" << endl;


    }

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

    return 0;
}
4

3 に答える 3

0

OS システムによっては、プログラムを実行するための特別な環境をセットアップして、時間がかかりすぎる場合 (または他の条件) にプログラムが終了するようにすることができます。または、必要なだけカウントダウンするスレッドを生成することもできます。終了してもメインスレッドがまだ実行されている場合は、そこからプログラムを強制終了できます。

于 2013-09-23T03:28:49.370 に答える
0

ctime私が推測するモジュールで簡単にそれを行うことができます：

#include <ctime>
#define HALF_HOUR 60 * 30
using namespace std;
...
clock_t start = clock();
clock_t now;
int i, j, tmp;
for (i = 1; i < length; i++) {
    j = i;
    while (j > 0 && arr[j - 1] > arr[j]) {
          now = clock();
          if ((now - start) / CLOCKS_PER_SEC) >= HALF_HOUR)
          {
              cout << "Insert sort timed out." << endl;
              return;
          }
          tmp = arr[j];
          arr[j] = arr[j - 1];
          arr[j - 1] = tmp;
          j--;
    }
于 2013-09-23T03:34:19.333 に答える
0

最も簡単な方法は、時限コールバック関数を実装することです。その関数は指定された時間間隔の後に呼び出され、その関数内でプログラムを終了できます。

実装方法の詳細については、次のリンクを参照してください。

c ++時限コールバック関数の実装

于 2013-09-23T03:35:11.013 に答える