Partition Algorithm

The purpose of the partition algorithm in Quickselectis to rearrange the elements of an array such that all elements less than a chosen pivot element are placed before it, and all elements greater than the pivot are placed after it.

The following is a linear-time implementation of the partition algorithm:

partition(A, p)
A: array of size n, p: integer such that 0 ≤ p < n
 
1. Create empty lists smaller, equal, and larger.
2. v ← A[p]  // Choose pivot element
3. for each element x in A
     if x < v then smaller.append(x)
     else if x > v then larger.append(x)
     else equal.append(x)
4. i ← smaller.size  // Number of elements smaller than the pivot
5. j ← equal.size    // Number of elements equal to the pivot
 
6. Overwrite A[0 ... i-1] by elements in smaller
7. Overwrite A[i ... i+j-1] by elements in equal
8. Overwrite A[i+j ... n-1] by elements in larger
 
9. return i  // Return the index of the pivot after partitioning
 

In this algorithm, we initialize three empty lists: smaller, equal, and larger. We choose the pivot element v from the array A at index p. Then, we iterate through all the elements in A and place them in the appropriate list based on their relationship with the pivot.

After the iteration, we know the sizes of the smaller and equal lists, which correspond to the number of elements smaller than and equal to the pivot, respectively. We overwrite the elements of A in three steps: first, with the elements in smaller, then with the elements in equal, and finally with the elements in larger. Finally, we return the index i which represents the index of the pivot after partitioning.

Partition algorithm used in Quickselect and Quick Sort.

Optional - In-Place partition (Hoare)

• Is Hoare’s in-place partition algorithm stable?
  • False
  • Suppose part of my array has something like $7,7,7$ and Hoare’s partition chose 2nd 7. First, it will move that 7 to the very end. At the end, we will place this second 7 into right place, but this will for sure will be left to first 7. Hence, this is not stable. Hope this helps!