# Quick Access

## Applications

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

# How To Build

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

# Visualization

# Complexity

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