Scenario

To better understand the partitioning method used in Snippet 2.7, walk through it one step at a time using an example.

Aim

Implement the Lomuto partitioning method in Java.

Steps for Completion

1. Run the code from Snippet 2.7, included in the code editor and shown below, for each element in the array by incrementing the values of variables x and i in the main() method.

2. Complete the following table, assuming that the pivot is the last element of the list, that is, 16:

3. i	Array	x
   -	[4,5,33,17,3,21,1,16]	-1
   0	[4,5,33,17,3,21,1,16]	0
   1
   2	[4,5,33,17,3,21,1,16]	1
   3
   4	[4,5,3,17,33,21,1,16]	2
   5
   6
   7
   final	[4,5,3,1,16,21,17,33]	3

   GIVEN CODE:

   import java.util.Arrays;

   public class QuickSort { public void sort(int[] numbers) { sort(numbers, 0, numbers.length - 1); }

   private void sort(int[] numbers, int start, int end) { if (start

   private int partition(int[] numbers, int start, int end) { int pivot = numbers[end]; int x = start - 1; for (int i = start; i

   private void swap(int[] numbers, int j, int k) { int temp = numbers[j]; numbers[j] = numbers[k]; numbers[k] = temp; }

   public static void main(String args[]) { QuickSort quickSort = new QuickSort(); int[] numbers = new int[]{4,5,33,17,3,21,1,16}; // Increment i (start) and x (end) here quickSort.partition(numbers, 0, 0); System.out.println(Arrays.toString(numbers)); }

   }

private int partition(int[] numbers, int start, int end) { int pivot = numbers[end]; int x = start - 1; for (int i = start; i