3

これは、私が 1 週間苦労して取り組んだラボの宿題です。この問題にはさらに多くのことがあり、私は迷っています。答えを求めるのではなく、何らかの方向にヒントを使用できます。間違ったことを投稿した場合は申し訳ありません。私の脳は揚げられています。どんな助けでも大歓迎です。

を。lesser と greater という 2 つの新しい配列を作成します。これらは、それぞれピボット要素より小さいまたは大きい「a」の要素を格納するために使用されます。

b. ピボット以外の "a" のすべての要素をループします。要素がピボットより小さい場合は、より小さい配列にコピーします。要素がピボット以上の場合は、それをより大きな配列にコピーします。

c. 「a」と同じ長さの、result という名前の新しい配列を作成します。

d. lesser の要素を結果にコピーします。

e. ピボット要素自体を結果にコピーします。

f. greater の要素を結果にコピーします。

g. 分割された配列の結果を返します。

このアルゴリズムpublic static double[] partition(double[] a)を実装するメソッドを書きます。

public class Lab6 {
public static void main(String[] args) {

}

public static double[] loadRandom(double[] randomNumbersArray)
{
    randomNumbersArray = new double[100000];

    // looping through to assign random values from 1 - 100000
    for (int i = 0; i < randomNumbersArray.length; i++) {
        randomNumbersArray[i] = (int)(Math.random() * 2000000000); 
    }

    return randomNumbersArray;
}

public static double[] partitionInPlace(double[] a)
{
    loadRandom(a);
    double pivotValue = a[0];
    int j = 0;  //j keeps track of which elements have already been placed

    //start by swapping the pivot value with the value at the rightmost index
    a[0] = a[a.length-1];
    a[a.length-1] = pivotValue;

    //go through the array (except for the rightmost index) to find the elements
    //that are < pivotValue
    for (int i = 0; i < a.length-1; i++) {
        //if a[i] is < pivotValue, then swap a[i] and a[j] and incremement j
        if (a[i] < pivotValue) {
            double temp = a[i];
            a[i] = a[j];
            a[j] = temp;

            j++;
        }
    }

    //now move the pivot back from its position on the right
    double temp = a[j];
    a[j] = a[a.length-1];
    a[a.length-1] = temp;

    //return the partitioned array
    return a;
}

public static double[] partition(double[] a) 
{
    double lesser;
    double greater;
    double result;

    return a;
}
}
4

2 に答える 2

3

alengthの配列から始めるとしますl。

次に、2 つの配列lesserと長さgreaterを作成する必要がありますl-1(すべての値がピボットよりも小さいか大きい可能性があるため)。

double[] lesser = new double[a.length() - 1];
double[] greater = new double[a.length() - 1];

その後は、(演習のように) データをこれらの配列にコピーするだけです。lesserlength = 0; greaterlength = 0;値を挿入するたびに、両方の配列の長さを追跡し、増加させます。lesserそうすれば、との次の値をどこに挿入できるかがわかりますgreater。

最終的に、 length の新しい配列に lesser をコピーできますl。

double[] result = new int[a.length()];

あなたはそれを知っていますlesserlength + 1 + greaterlength == a.length()

結果にandSystem.arraycopy(source, srcpos, dest, dstpos, len)をコピーするために使用できます。lessergreater

それはあなたを助けるのに十分なはずです.

于 2013-07-30T14:36:57.700 に答える