CODEWITHSUNDEEP
java
Ponyboy Curtis
Ponyboy Curtis

Reputation: 31

Partition an array with this algorithm

This is a lab homework assignment that I have struggled with for a week now. There is more to this problem and I am lost. I could use a hint in some direction, not asking for the answer. My apologies if I've posted something incorrectly, my brain is fried. Any help at all would be appreciated.

a. Create two new arrays called lesser and greater. These will be used to store the elements of "a" that are less than or greater than the pivot element, respectively.

b. Loop through all elements of "a" besides the pivot. If the element is less than the pivot, copy it into the lesser array. If the element is greater than or equal to the pivot, copy it into the greater array.

c. Create a new array called result, of the same length as "a".

d. Copy the elements of lesser into result.

e. Copy the pivot element itself into the result.

f. Copy the elements of greater into result.

g. Return the partitioned array result.

Write a method public static double[] partition(double[] a) that implements this algorithm.

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;
}
}

Upvotes: 3

Views: 930

Answers (2)

NickJ
NickJ

Reputation: 9559

This should do the trick:

private static double[] partition(double[] a) {

    //choose some pivot, perhaps randomly?
    Random r = new Random();
    double pivot = a[r.nextInt(a.length)];

    //create lesser and greater arrays
    double[] lesser = new double[a.length];
    double[] greater = new double[a.length];

    //loop through members of a
    int lesserIndex = 0;
    int greaterIndex = 0;

    for (double number : a) {
        if (number < pivot) {
            lesser[lesserIndex++] = number;
        } else {
            greater[greaterIndex++] = number;
        }
    }

    //create result array
    double[] result = new double[a.length];
    int resultIndex = 0;

    //copy in lesser
    for (int i=0; i<lesserIndex; i++) {
        result[resultIndex++] = lesser[i];
    }

    //copy in pivot
    result[resultIndex++] = pivot;

    //copy in greater
    for (int i=0; i<greaterIndex; i++) {
        result[resultIndex++] = greater[i];
    }

    //return result
    return result;

}

Upvotes: 2

bas
bas

Reputation: 1678

Say you start with an array a with length l.

Then you should create two arrays lesser and greater with l-1 length (since all values could be smaller or larger than the pivot).

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

After that, it is simply (as in your exercise) copying the data to these arrays. Keep track of the length of both arrays like lesserlength = 0; greaterlength = 0; and incrementing that each time you insert a value. That way you know where you can insert the next value in lesser and greater.

Eventually you can copy lesser into a new array of length l.

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

You know that lesserlength + 1 + greaterlength == a.length()

You can use System.arraycopy(source, srcpos, dest, dstpos, len) to copy lesser and greater into the result.

That should be enough to help you out.

Upvotes: 3

Related Questions