Question

(7 pts) Problem 1 Consider this algorithm for partitioning an array a: 1. Create two new lesser and greater arrays. These will be used to store the elements of a that are sor > the pivot element, respectively. 2. Loop through all elements of a besides the pivot. If the element is the pivot, copy it into lesser. If the element is > the pivot, copy it into greater. 3. Create a new result array, of the same length as a. 4. Copy the elements of lesser into result, then the pivot into result, and finally the elements of greater into result. 5. Return the array result. Note that this algorithm doesn't affect the original array a; it just creates a new array containing the partitioned version of a Within your ArrayPartitioning java class, write a method partition (int) a) that implements

Answer 1

As per the question we need to devide array in two different array which contain element

1) lesser from Pivot

2) greater from Pivot

3)resultant array should be size of input array

Since there is no mention of sorting in question so i divide array simply into two wihtout any sorting

here is the code :

import java.util.Arrays;
import java.io.*;
import java.lang.*;
import java.util.*;

public class test
{
  

public static void main(String args[])
{
int x= 0;
int y =0;
  
int nums[] = {10, 3, 4, 12, 1, 18, 20};
int pivot = nums[0];
  
int[] lesser = new int[10];

int[] greater = new int[10];

for(int i = 0; i< nums.length ; i++ )
{

if (nums[i]<=pivot)
{
lesser[x]= nums[i];
x= x+1;
  
}
else
{
greater[y]= nums[i];
y =y+1;
}

}
int z = 0;
int[] result = new int[nums.length];
for (int k = 0; k<lesser.length ; k++)
{
result[z]= lesser[k];
z= z+1;
if (k==x-1)
{
break;
}
}
for (int k = 0; k<greater.length ; k++)
{
result[z]= greater[k];
z= z+1;
if (k==y-1)
{
break;
}
}


System.out.println(Arrays.toString(result));

}
}