Traces by a Partition-Exchange on random sequence

Swaps by a Partition-Exchange on random sequence

Traces by a Partition-Exchange on reversed sequence

Swaps by a Partition-Exchange on reversed sequence

Applications

• Used as a subroutine in finding the Kth Minumum/Maximum Element.
• Used as a subroutine in the Quick Sort algorithm.

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 higher 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.

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;
 }
} 

1. At the start of the partition, the pivot (the median) is moved to the end (bottom).

2. All elements less than the pivot goes left to the pointer.

3. The pivot is put back at the new pointer position.

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.