6

事前にソートされた8つのアレイをマージしようとしています。私はCにかなり慣れていませんが、これは私がこれまでに思いついたものです。言うまでもなく、それは機能しません。私が理解できないのはその理由です。ここではC++マージソートの実装に基づいており、8次元に拡張して少し単純化しようとしましたが、何らかの理由で最初の配列の要素が表示され、その後に34、30が続き、23が繰り返されます。終わりまで。21が最初の反復で最小値であることを認識していません。

int test1[5] = {23, 24, 25, 33, 51};
int test2[5] = {21, 34, 44, 50, 62};
int test3[5] = {34, 36, 41, 44, 46};
int test4[5] = {30, 31, 32, 35, 40};
int test5[5] = {54, 56, 57, 58, 60};
int test6[5] = {31, 33, 36, 51, 52};
int test7[5] = {44, 46, 76, 78, 79};
int test8[5] = {23, 33, 43, 54, 63};

int output[40];
int t1, t2, t3, t4, t5, t6, t7, t8;
t1 = 0;
t2 = 0;
t3 = 0;
t4 = 0;
t5 = 0;
t6 = 0;
t7 = 0;
t8 = 0;
int p = 0;
int temp1;
int temp2;

while(p < 40) {
    if (t1 < 5) {
        temp1 = 1;
        temp2 = test1[t1];
    }else if (test2[t2] <= test1[t1] && t2 < 5) {
        temp1 = 2;
        temp2 = test2[t2];
    }else if (test3[t3] <= temp2 && t3 < 5) {
        temp1 = 3;
        temp2 = test3[t3];
    }else if (test4[t4] <= temp2 && t4 < 5) {
        temp1 = 4;
        temp2 = test4[t4];
    }else if (test5[t5] <= temp2 && t5 < 5) {
        temp1 = 5;
        temp2 = test5[t5];
    }else if (test6[t6] <= temp2 && t6 < 5) {
        temp1 = 6;
        temp2 = test6[t6];
    }else if (test7[t7] <= temp2 && t7 < 5) {
        temp1 = 7;
        temp2 = test7[t7];
    }else if (test8[t8] <= temp2 && t8 < 5) {
        temp1 = 8;
        temp2 = test8[t8];
    }
    switch(temp1) {
        case 1:
            output[p] = temp2;
            t1++;
            break;
        case 2:
            output[p] = temp2;
            t2++;
            break;
        case 3:
            output[p] = temp2;
            t3++;
            break;
        case 4:
            output[p] = temp2;
            t4++;
            break;
        case 5:
            output[p] = temp2;
            t5++;
            break;
        case 6:
            output[p] = temp2;
            t6++;
            break;
        case 7:
            output[p] = temp2;
            t7++;
            break;
        case 8:
            output[p] = temp2;
            t8++;
            break;
    }
    printf("%d\n",  output[p]);
    p++;
}

あなたが提供できるどんな助けにも感謝します。

4

3 に答える 3

4

これが、最初の配列の最初の5つの要素を取得する理由です。

if (t1 < 5) {
        temp1 = 1;
        temp2 = test1[t1];

あなたのコードは、最初の配列の最初の5つの要素が最初に選択されることを明確に保証しています。test1の次の要素の値を、盲目的に選択するだけでなく、他の配列の次の要素と比較する必要があります。また、if..then..else if .. elseif...の使用は正しくありません。配列2の次の要素が配列1の次の要素よりも小さいことがわかった場合でも、配列3、4、および5が小さいかどうかを調べる必要があります。

このようにコードを構造化してみてください

int temp1 = -1;
if (t1 < 5) {
    temp1=1;
    temp2=test1[t1];
}
if ((t2 < 5) && ((temp1 < 0) || (test2[t2] < temp2))) {
    temp1=2;
    temp2=test2[t2];
}
if (t3...

その後に既存のswitchステートメントが続きます。

于 2012-05-27T14:24:37.500 に答える
3

手斧はすでに何が悪かったのかを教えてくれました。2番目の条件が有効で最初のif ... else if ...条件が無効だった場合にのみ、2番目のブロックを実行します。

ただし、別の配列のセットを並べ替えるには、すべての固定フィールドと値を変更する必要があるためswitch()、if-elseベースのプログラムを拡張するのは少し難しいと思います。次のプログラム/関数はあなたのものと同じものを提供しますが、拡張するのが簡単です。追加の配列cursorを使用して現在の位置を保存します（、、、 ...と同様t1）t2（Ideone Demo）。

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

int multimerge(
    int * const * const arrays,      // arrays holding the data
    int const * const arraysizes,    // sizes of the arrays in `arrays`
    int number_of_arrays,            // number of arrays
    int * const output               // pointer to output buffer
){
    int i = 0;       // output cursor
    int j = 0;       // index for minimum search
    int min;         // minimum in this iteration
    int minposition; // position of the minimum

    // cursor for the arrays
    int * cursor = calloc(number_of_arrays,sizeof(int));

    if(cursor == NULL)
        return -1;

    while(1){
        min = INT_MAX;
        minposition = -1; // invalid position

        // Go through the current positions and get the minimum
        for(j = 0; j < number_of_arrays; ++j){

            if(cursor[j] < arraysizes[j] &&  // ensure that the cursor is still valid
               arrays[j][cursor[j]] < min){  // the element is smaller
                min = arrays[j][cursor[j]];  // save the minimum ...
                minposition = j;             // ... and its position
            }
        }

        // if there is no minimum, then the position will be invalid

        if(minposition == -1)
            break;

        // update the output and the specific cursor            
        output[i++] = min;
        cursor[minposition]++;
    }
    free(cursor);

    return 0;
}

int main()
{
    int i = 0;
    int test1[5] = {23, 24, 25, 33, 51};
    int test2[5] = {21, 34, 44, 50, 62};
    int test3[5] = {34, 36, 41, 44, 46};
    int test4[5] = {30, 31, 32, 35, 40};
    int test5[5] = {54, 56, 57, 58, 60};
    int test6[5] = {31, 33, 36, 51, 52};
    int test7[5] = {44, 46, 76, 78, 79};
    int test8[5] = {23, 33, 43, 54, 63};

    int *test[] = {test1, test2, test3, test4, test5, test6, test7, test8};
    int testsizes[] = {5,5,5,5,5,5,5,5};

    int output[40];

    multimerge(test,testsizes,8,output);

    while(i < 30){
        printf("%i\n",output[i++]);
    }    

    return 0;
}
于 2012-05-27T14:55:01.360 に答える
2

私が（遠い）過去に行ったことは、各リストの最初の要素をタグソートで並べ替え、並べ替えられたリストの最初の要素を選択してマージされたリストに追加し、移動されたアイテムをからの次の要素に置き換えることですそのリスト（これが、置換がどこから来るべきかを識別するために、何らかのフレーバーのタグソートが必要な理由です）そして再ソートします。ヘッド要素の並べ替えは、バブルソートを使用して行うことができます。これは、最初の並べ替えの後、削除/交換後に適切に並べ替えるのに1回のパスで済むためです。

于 2012-05-27T14:12:41.473 に答える