This homework deals with the problem of partitioning an arra

This homework deals with the problem of partitioning an array. We\'ll define partitioning to mean arranging the elements of an array around a certain \"pivot\" element such that all elements to the left of the pivot are strictly less than the pivot, and all elements to the right of the pivot are greater than or equal to the pivot. To simplify things a little bit, we\'ll assume that the pivot element is always the first element (index 0) of the original array (i.e., before any rearranging of elements is performed). For example, suppose you have an array containing the elements {10, 7, 45, -44, 33, 1}. Here the pivot would k be the original first element, which is 10. If I asked you to partition this array, here are some possible results: {7, 1, -44, 10, 45, 33} {-44, 1, 7.10, 45, 33} f {1, 7, -44, 10, 33, 45}Note that there\'s more than one valid way to partition - the only requirement is that all elements to the left of the pivot are less than the pivot, and all elements to the right of the pivot are greater than or equal to the pivot. Also note that partitioning is NOT the same as sorting the array - sorting means to arrange the array elements such that they are all in order from least to greatest. As you can see from the examples above, partitioning alone does not guarantee this. However, partitioning is an important first step in some sorting algorithms! Consider this algorithm for partitioning an array 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. 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. Create a new array called result, of the same length as a. Copy the elements of lesser into result. Copy the pivot element itself into result. Copy the elements of greater into result. Return the partitioned array result. Write a method public static[] doubled partition(double[] a) that implements this algorithm.

Solution

public static double[] partition(double[] a) {
       // TODO Auto-generated method stub
       double[] lesser=new double[200];
       double[] greater=new double[200];
       double[] result=new double[200];
       int j=0,k=0,m=0;
       double pivot=a[0];
       for(int i=1;i<a.length;i++)
       {
           if(pivot<a[i])
               greater[j++]=a[i];
           else
               lesser[k++]=a[i];
       }
      
       for(int i=0;i<lesser.length;i++)
           result[m++]=lesser[i];
      
       result[m++]=pivot;
      
       for(int i=0;i<greater.length;i++)
           result[m++]=greater[i];
       return result;
      
      
   }