Chapter 7 Exercise 32, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

**7.32 (Partition of a list) Write the following method that partitions the list using the first element, called a pivot. public static int partition(int[] list) After the partition, the elements in the list are rearranged so that all the elements before the pivot are less than or equal to the pivot and the elements after the pivot are greater than the pivot. The method returns the index where the pivot is located in the new list. For example, suppose the list is {5, 2, 9, 3, 6, 8}. After the partition, the list becomes {3, 2, 5, 9, 6, 8}. Implement the method in a way that takes at most list.length comparisons. Write a test program that prompts the user to enter a list and displays the list after the partition. Here is a sample run. Note that the first number in the input indicates the number of the elements in the list. This number is not part of the list.

Enter list: 8 10 1 5 16 61 9 11 1
After the partition, the list is 9 1 5 1 10 61 11 16

import java.util.Scanner;
 
 
 
public class ProgrammingEx7_32 {
 
 public static void main(String[] args) {
  Scanner input = new Scanner(System.in);
  System.out.print("Enter list:");
  int[] list1 = new int[input.nextInt()];
  for (int i = 0; i < list1.length; i++) {
   list1[i] = input.nextInt();
  }
   
  partition(list1);
   
  System.out.print("After the partition, the list is ");
   
  for (int i = 0; i < list1.length; i++) {
   System.out.print(list1[i] + " ");
  }
 
 }
  
 public static int partition(int[] list) {
  int partition = list[0];
  int partitionLocation = 0;
  int hi = list.length-1;
   
  while(partitionLocation < hi) {
    
   if(partition>list[partitionLocation+1]) {
    //swap partition and the next item
    list[partitionLocation] = list[partitionLocation+1];
    list[partitionLocation+1] = partition;
    partitionLocation++;
   } else {
    //move the item to the end of the list
    int temp = list[hi];
    list[hi]=list[partitionLocation+1];
    list[partitionLocation+1] = temp;
    hi--;
       
   }
  }
   
  return partitionLocation;
  
 }
 
}