Partitioning data around an element is a common operation used in several fundamental algorithms in computer science. Given a vector of integers, \( A \), of size \( N \), and an index \( p \) between 0 and \( N - 1 \), partitioning involves rearranging the elements of \( A \) such that all elements with indices \( i \) where \( 0 \leq i < N \) are divided into two groups: those less than or equal to \( A[p] \) (the pivot) are placed on one side, and those greater than \( A[p] \) are placed on the other side. The element \( A[p] \) is referred to as the pivot.
Let A = [9, 3, 7, 6, 2, 8, 1, 4, 5, 10] with pivot index p = 2 (pivot = 7).
Original:
A = [9, 3, 7, 6, 2, 8, 1, 4, 5, 10]
All of the following partitions are valid:
A = [1, 3, 2, 5, 6, 4, 7, 9, 10, 8]
A = [6, 2, 1, 3, 5, 4, 7, 10, 8, 9]
A = [4, 1, 5, 2, 3, 6, 7, 9, 10, 8]
In all these cases, the elements less than or equal to the pivot (7) are on the left, while the elements greater than 7 are on the right, though their relative order differs.
The goal is often to partition the data in-place. This means that the data is rearranged directly within the original structure, reducing memory overhead. By doing so, algorithms can be more efficient, especially when handling large datasets, as no extra space is required for a copy of the data, and three is no need to allocate/deallocate additional memory, which will slow down the program.
Following is a description of a method for in-place partition. The description is deliberately kept at a high level; details need to be worked out.
In-place partition using two indices
Keep an index \( l \) (left) on the left side, and an index \( r \) (right), on the right side of the vector, \( A \).
Determine if \( A[l] \) and \( A[r] \) should be swapped, based on the value of the pivot.
(Be careful regarding where \( l \) and \( r \) should begin, and when the loop should terminate)Return the index of partition, \( k \), such that: \( \forall i \, (i < k) \), \( A[k] \leq \text{pivot} \), and \( \forall i \, (i> k) \), \( A[i] > \text{pivot} \). The index \( k \) is called the partition index and contains the pivot element.
The following code contains an empty function (to be implemented by you), and a main that tests it.