Consider this algorithm for partitioning an array a : a. Creatre two new arrays
ID: 3540158 • Letter: C
Question
Consider this algorithm for partitioning an array a:
a. Creatre 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 though 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 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.
As you may have guessed, the above algorithm isn't very efficient. It requires a lot of extra memory to create the new arrays for keeping track of lesser and greater elements. This also requires extra time. Fortunately, it's possible to do an in-place partition, meaning that the original array is partitioned without needing to use extra temporary arrays.
For each version of partition, write a program that determines the average time required to partition an array of 100,000 random numbers Compute this average based on 1,000 different arrays. Your program should perform the following actions:
a. Repeat for 1,000 times:
i. Create a new array of 100,000 random numbers
ii. Start your stopwatch
iii. Call a partition method on your array
iv. Stop your stopwatch
v. Compute the time elapsed
b.Find the average time elapsed over each of the 1,000 different arrays
Explanation / Answer
public class PartB {
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < 1000; i++)
{
double[] array = new double[10000];
for (int j = 0 ; j < 10000 ; j++)
{
array [j] = (int) (Math.random () * 10000);
}
double[] result = new double[10000];
result = Array.partition(array);
}
long endTime = System.currentTimeMillis();
System.out.println("Took "+(endTime - startTime) + " milliseconds");
}
public static double[] partition(double[] a)
{
double pivot = 500.0;
double[] lesser = new double[10000];
double[] greater = new double[10000];
double[] result = new double[10000];
int j = 0, k= 0, m = 0;
for (int i =0; i < a.length; i++){
if (a[i]>= pivot)
{
greater[j] = a[i];
j++;
}else
{
lesser[k] = a[i];
k++;
}
}
System.out.println(j +" and "+k);
for (int i = 0; i <k; i++){
result[m] = lesser[i];
m++;
}
System.out.println(m);
result[m] = pivot;
System.out.println(m);
for (int i = 0; i <j; i++){
result[m] = greater[i];
m++;
}
return result;
}
}