Beginning Java Data Structures and Algorithms

Quicksort Partitioning

Partitioning is the process by which we reorder our array so that elements with a value less than our pivot are moved to the left of the pivot and those with a larger value are moved to the right (see Figure 2.2). There are numerous manners in which we can do this. Here, we will describe an easy-to-understand scheme known as Lomuto Partitioning.

Take a look at this diagram:

Figure 2.2: Before and after partitioning of an array

Many other schemes exist. The Lomuto scheme has the drawback that it is not very performant when it is used on already-sorted lists. The original Hoare partition scheme performs better and works ...