The Partition Subroutine

Internal

• Algorithms

Problem Statement

Given an array and an element of it - the pivot element - rearrange the array so it has the following property: any element that is at the left of the pivot should be smaller or equal with the pivot, and any element that is at the right of the pivot should be grater that the pivot.

Discussion

After partitioning, the pivot element ends up in its rightful position in the (eventually) sorted array. The implementation is linear time and in-place. The partition subroutine is an essential part of the Quicksort algorithm.