Beginning Java Data Structures and Algorithms

Activity: Understanding the Partitioning Method

Scenario

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

Aim

To understand how the Lomuto partitioning works.

Steps for completion

1. Dry run the code mentioned in Snippet 2.7 for each element in the array by incrementing the values of variables x and i.
2. Complete the following table, assuming that the pivot is the last element of the list, that is, 16:

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

Table 2.1: Steps through the partitioning method ...