Question

write a completed JAVA program (Main included) and make it not interactive but straight to the output

Write a method called partition that accepts a list of integers and an integer value E as its parameter, and rearranges (partitions) the list so that all the elements with values less than E occur before all elements with values greater than E The exact order of the elements is unimportant, so long as all elements less than E appear before all elements greatr bau E. For example, for the linked list [15, 1, 6, 12, -3, 4, 8, 21, 2, 30, -1, 9], one acceptable ordering of the list after a call of partition(list, 5) would be [-1, 1, 2, 4, -3, 12, 8, 21, 6, 30, 15, 9]. You may assume that the list contains no duplicates and does not contain the element value E.

Answer 1

This problem is similar to partitioning an array in quick sort .

only difference between quicksort partition function and this problem's partiton method is that in this method, pivot is given in addition to the list, whereas in quicksort partiton we take one element of array to be pivot.

we place pivot element at a position such that position previous to pivot have values smaller than pivot, and position ahead of pivot have values larger than pivot

(order is not important)

Below is the java code for implementing partition function:

import java.util.ArrayList;
import java.util.Scanner;

public class partition {

   public static void main(String args[]){
       ArrayList<Integer> list=new ArrayList<Integer>();
       int size,element,E;
       Scanner sr= new Scanner(System.in);
       size=sr.nextInt(); //input size of list
       for(int i=0;i<size;++i){
           element=sr.nextInt(); //inputing the list element by element
           list.add(element);
       }
       E=sr.nextInt(); //input pivot value to partition the list

         for(int i=0;i<list.size();++i)// printing original list

       {
           System.out.print(list.get(i)+" ");
       }

        System.out.println();

       partitionlist(list,E); //function call

       for(int i=0;i<list.size();++i) //printing list after partition is done

        {
           System.out.print(list.get(i)+" ");
       }
       System.out.println();
       sr.close();
   }

   static void partitionlist(ArrayList<Integer> list, int E)
   {
      
       int i=-1,j,temp;
       for(j=0;j<list.size();++j)
       {
           if(list.get(j)<=E)
           {
               ++i;
               temp=list.get(j);
               list.set(j,list.get(i));
               list.set(i,temp);
           }
       }
   }
}