Partition an array with this algorithm

Question

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

• Tala: Do you want us to code review?
• atk: @PonyboyCurtis: Are you intentionally doing things differently from how the instructions instruct? Can you try again, from scratch, doing literally exactly what the instructions say to do without substantial interpretation? For example, in step 1 it says to create two arrays named lesser and greater, but you instead have those as doubles in your partition() method...
• Ponyboy Curtis: I need to create the last method, partition, by the algorithm posted. I'm not sure where to begin with it. When that algorithm is complete, I have to create an array of 100,000 random numbers and partition using both methods then find the average time elapsed over each of the 1,000 different arrays.
• Sam I am says Reinstate Monica: the first part of your assignment says Create two new arrays called lesser and greater.. You should do that
• Ponyboy Curtis: Thank you. I will try starting again from scratch. I'm afraid I'm having more trouble than I can save myself from.

Answer 1

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.

• Ponyboy Curtis: Thank you! I am going to use this to try to get somewhere now. Appreciated greatly.

Answer 2

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

• Ponyboy Curtis: This actually does seem to do the trick. I needed an extra little push. I am working on the rest now. Everyone's help is so appreciated. Thank you, NickJ.