"I want the solution to be in JAVA with explination please "

Problem 1: Partitioning (Phase I)

To partition an array, first choose one integer from the array and call it the pivot. Next, manipulate the array so that all integers less than the pivot are in the left part of the array and all numbers greater than or equal to the pivot are in the right part of the array. Finally, place the pivot in-between the two parts.

Heres an example. We choose the first integer as the pivot.

Original array:

15

9

42

31

7

5

88

16

11

3

0

19

33

45

2

66

13

8

12

18

The pivot is 15. Partitioned array:

9

7

5

11

3

0

2

13

8

12

15

18

66

45

33

19

16

88

31

42

(Side note: Observe that, if we sort the array, the pivot will not move. Its in the right place!)

Write a method that partitions a given array of integers. It returns the index of the pivot.

public static int partition(int[] a)

Hint #1: Use the merge method as an example. You can create a second array to hold the partitioned numbers and then copy the numbers from the second array back into the first.

Hint #2: Maintain 3 indices: left, right and i. Use i to traverse the given array. Use left and right to determine where in the second array to place the numbers from the given array. The left index identifies where to place integers smaller than the pivot. The right index identifies where to place integers that are greater than or equal to the pivot.

Hint #3: Dont forget to place the pivot element in the second array!

Hint #4: Always choose the first integer in the array as the pivot.

Hint #5: This is not a recursive method.

Test your method before continuing!

Problem 2: Partitioning (Phase II)

Generalize your partition method so that it works for a specified array range rather than the entire array.

public static int partition(int[] a, int start, int end)

Only partition the integers in the array between index start and index end, inclusive.

Problem 3: Quick Sort!

The partition method (from Phase II) is used by the QuickSort algorithm. This sorting algorithm is very similar to MergeSort:

If the array has at least two elements:

Partition the array

QuickSort the left part

QuickSort the right part

Implement the QuickSort algorithm.

TEST YOUR METHODS!!!