Applications

Partition-exchange algorithm reorders the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position.

Steps

  • 1. Put the pivot at the end for convenience.
  • 2. Create a pointer pointing at the beginning.
  • 3. For each value, if value <= pivot:
    • Swap value with the one under the pointer.
    • Increment pointer position.
  • 4. Put back the pivot at the pointer position.

Pseudo-Code

Iterator Partition (Iterator begin, Iterator pivot, Iterator end)
{
  if (distance(begin, end) < 2 || pivot == end)
    return pivot;

  auto pivotValue = *pivot;  // Keep the pivot value;
  swap(*pivot, *(end - 1));  // Put the pivot at the end for convenience
  auto store = begin;        // Put the store pointer at the beginning

  // Swap each smaller before the pivot item
  for (auto it = begin; it != end - 1; ++it)
  {
    if (Compare(*it, pivotValue))
    {
      swap(*store, *it);
      ++store;            // Increment store position
    }
  }

  // Replace the pivot at its good position
  swap(*(end - 1), *store);

  return store;
 }
} 

Time

Partition-Exchange has to go through all element only once, it then requires O(n) time in all cases.

Space

Partition_Exchange does not use any buffer nor does make any recursion. Thus, it requires O(1) space in all cases.