2

私は、Javaで3方向マージショートのようなものを実装する割り当てとして持っています。入力として整数の配列を持ち、次のことを行う必要があります。

3 方向分割を使用して配列にマージソートを実装し、配列の 3 つの並べ替えられたパーティションも出力します。たとえば、入力として次の配列[9 23 10 90 70 10 3 23]がある場合、出力は最初に 3 つのパーティションが並べ替え[9 10 24] [70 90] [3 10 23]られ、次に最終的な配列が並べ替えられ[3 9 10 10 23 24 70 90]ます。

これは私がこれまでに実装したものです：

public static void mergesort(int[] data) {
    int elements = data.length - 1;
    int length1;
    int length2;
    int length3;

    if (elements % 3 == 0) {
        length1 = elements / 3;
        length2 = elements / 3;
        length3 = elements / 3;
    } else if (elements % 3 == 1) {
        length1 = (elements / 3) + 1;
        length2 = elements / 3;
        length3 = elements / 3;
    } else { //if (elements % 3 == 2)
        length1 = (elements / 3) + 1;
        length2 = elements / 3;
        length3 = (elements / 3) + 1;
    }

    Arrays.sort(data, 0, length1 - 1);
    Arrays.sort(data, length1, length1 + length2 - 1);
    Arrays.sort(data, length1 + length2, length1 + length2 + length3 - 1);

    merge(data, 0, length1, length1 + length2);
    merge(data, 0, length1 + length2, length1 + length2 + length3);
}

private static void merge(int[] data, int first, int n1, int n2) {
    int[] temp = new int[n1 + n2];
    int copied = 0;
    int copied1 = 0;
    int copied2 = 0;
    int i;

    while ((copied1 < n1) && (copied2 < n2)) {
        if (data[first + copied1] < data[first + n1 + copied2]) {
            temp[copied++] = data[first + (copied1++)];
        } else {
            temp[copied++] = data[first + n1 + (copied2++)];
        }
    }

    while (copied1 < n1) {
        temp[copied++] = data[first + (copied1++)];
    }
    while (copied2 < n2) {
        temp[copied++] = data[first + n1 + (copied2++)];
    }

    for (i = 0; i < n1 + n2; i++) {
        data[first + i] = temp[i];
    }
}

私が行ったことは、まず状況に応じて配列を 3 つの部分に分割し、その後、配列の 3 つの部分を並べ替えてから、最初の 2 つの部分をマージしてから、結合した部分を最後の部分とマージします。

私は初心者のためにこれら2つの方法を実装しましたが、まず第一に、マージ方法がひどく間違っていると確信しています.2番目に、この問題での私のアプローチに何か問題があると思います.マージソート方法でさえ間違っていると感じています.めちゃめちゃ実装。

私が欲しいのは、この問題で何をすべきか、実装の何が完全に間違っているかについてのアドバイスです

4

1 に答える 1

2 
void merge(int arr1[], int arr2[])
{
  int p1 = 0;
  int p2 = 0;
  int arr3[] = new int[arr1.length + arr2.length];

  while(p1 < arr1.length && p2 < arr2.length)
  {
    if(arr1[p1] > arr2[p2])
    {
      arr3[p2] = arr2[p2];
      p2++;
    }
    else
    {
      arr3[p1] = arr1[p1];
      p1++;
    }
  }

  //Now just add the code for just concatenating any remaining elements in 
  // either arr1 or arr2
  //This will happen if the lengths of arr1 and arr2 differ 


}

これは、2 つの配列をマージするための基本的なコードです (テストされていないため、境界条件を見逃す可能性があります)。コードに組み込んでみてください。

于 2012-05-17T15:42:50.593 に答える