Offensive Security Researcher & Quantum Cryptography Analyst

Partitioning Algorithm: Working, Explanation, and Implementation Guide

Abdul Wahab Junaid
Partitioning algorithm and working of this algorithm

Partitioning algorithm and working of this algorithm

I want to explain partitioning as one of the more general and widely reused ideas in computer science and operations research: the problem of dividing a set of items, a graph, or a dataset into distinct, non-overlapping groups (partitions) that satisfy some optimality or balance criterion. I find it important because it underlies everything from the “divide” step of divide-and-conquer sorting algorithms, to graph partitioning for parallel computing, to balanced workload assignment in distributed systems.

History and Background

Partitioning as a mathematical idea traces back to combinatorics and number theory (the study of integer partitions goes back to Euler in the 18th century), but the algorithmic partitioning I focus on here — set/graph partitioning for optimization — became prominent in the mid-20th century alongside the growth of operations research and computer science. Tony Hoare’s Quicksort (1960) popularized the partition step as a core algorithmic primitive, while graph partitioning as an optimization problem was formalized in the 1970s, with the Kernighan–Lin algorithm (1970) becoming one of the most influential heuristic methods for balanced graph partitioning, later refined by Fiduccia and Mattheyses in 1982.

Problem Statement

I describe the general partitioning problem as: given a set $S$ (or a graph $G$), divide it into $k$ disjoint subsets $S_1, S_2, \dots, S_k$ such that $\bigcup_i S_i = S$ and $S_i \cap S_j = \emptyset$ for $i \neq j$, while optimizing some objective — commonly minimizing the “cost” of the partition (e.g., edges cut between subsets in graph partitioning, or the difference between subset sums in number partitioning) subject to balance constraints (e.g., roughly equal subset sizes).

Core Concepts

How It Works

I’ll describe the two most common forms I encounter:

A. Quicksort-style array partitioning (Lomuto scheme):

  1. I choose a pivot element, often the last element of the array segment.
  2. I maintain an index marking the boundary of elements known to be smaller than the pivot.
  3. I scan through the array; whenever I find an element smaller than the pivot, I swap it into the boundary region and advance the boundary index.
  4. At the end, I swap the pivot into its correct final position, which now separates the “smaller” and “larger” groups.

B. Graph/set partitioning (Kernighan–Lin style):

  1. I start with an initial partition (often random or based on natural ordering) into two roughly equal-sized groups.
  2. I compute the gain of swapping each pair of nodes (one from each group) — the reduction in cut size that swap would produce.
  3. I repeatedly perform the swap with the highest gain, locking the swapped nodes so they aren’t moved again in this pass.
  4. After all nodes are locked, I look back at the sequence of swaps and pick the prefix that gave the greatest cumulative cut reduction.
  5. I repeat these passes until no further improvement is found.

Working Principle

The underlying logic in both cases is a form of local, incremental refinement guided by a well-defined objective function. In the array case, the objective is “is this element on the correct side of the pivot,” resolved through a single linear scan. In the graph case, the logic is a greedy local search: I always take the locally best-looking move, but I allow temporarily “bad” moves within a pass (since gains can go negative before rising again) so that the algorithm can escape shallow local optima — this is the key insight that separates Kernighan–Lin from naive greedy swapping.

Mathematical Foundation

For array partitioning around pivot $p$, correctness after processing requires:

$$ \forall i < \text{pivot index}: A[i] \leq p \quad \text{and} \quad \forall i > \text{pivot index}: A[i] > p $$

For graph partitioning into two balanced sets $A$ and $B$, I define the cut size as:

$$ \text{cut}(A,B) = \sum_{i \in A, j \in B} w_{ij} $$

where $w_{ij}$ is the edge weight between nodes $i$ and $j$. The objective is:

$$ \min_{A,B} \ \text{cut}(A,B) \quad \text{subject to} \quad \big| |A| – |B| \big| \leq 1 $$

For the gain-based swap used in Kernighan–Lin, the gain $g$ of swapping node $a \in A$ with node $b \in B$ is:

$$ g(a,b) = D(a) + D(b) – 2 w_{ab} $$

where $D(x)$ is the difference between external and internal edge costs of node $x$.

Diagrams

flowchart TD
    Start([Start: initial partition]) --> Gain[Compute swap gains for all pairs]
    Gain --> Best[Select and apply best-gain swap, lock nodes]
    Best --> More{Unlocked nodes remain?}
    More -- Yes --> Gain
    More -- No --> Prefix[Find prefix of swap sequence with max cumulative gain]
    Prefix --> Apply[Apply that prefix permanently]
    Apply --> Improve{Improvement found this pass?}
    Improve -- Yes --> Start
    Improve -- No --> End([Return final partition])

Pseudocode

Array partition (Lomuto scheme):

function Partition(A, low, high):
    pivot = A[high]
    i = low - 1
    for j from low to high - 1:
        if A[j] <= pivot:
            i = i + 1
            swap(A[i], A[j])
    swap(A[i+1], A[high])
    return i + 1  // final pivot index

Graph partition (Kernighan–Lin, simplified):

function KernighanLin(Graph, A, B):
    improved = true
    while improved:
        improved = false
        unlocked = all nodes
        gains = []
        while unlocked is not empty:
            (a, b) = pair in A x B with max gain(a, b)
            record swap(a, b) and its gain
            lock a, b
            update gains of remaining unlocked nodes
        find prefix of recorded swaps with maximum cumulative gain
        if that cumulative gain > 0:
            apply the swaps in that prefix to A, B
            improved = true
    return A, B

Step-by-Step Example

Array partition example: Array = [8, 3, 5, 1, 9, 2], pivot = 2 (last element).

Time Complexity

Space Complexity

Correctness Analysis

For array partitioning, correctness follows directly from the loop invariant: at the start of each iteration, all elements in $A[low..i]$ are $\leq$ pivot, and all elements in $A[i+1..j-1]$ are $>$ pivot; this invariant is maintained by the swap logic and, upon loop termination, guarantees the pivot lands in its correct sorted position. For Kernighan–Lin partitioning, there is no guarantee of a globally optimal cut (the problem is NP-hard in general), but each pass is guaranteed to never increase the cut size, since I only keep the prefix of swaps with positive cumulative gain — so the algorithm converges monotonically to a local optimum.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>

// Swap two integers
void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

// Lomuto partition scheme
int partition(int A[], int low, int high) {
    int pivot = A[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (A[j] <= pivot) {
            i++;
            swap(&A[i], &A[j]);
        }
    }
    swap(&A[i + 1], &A[high]);
    return i + 1;
}

void quicksort(int A[], int low, int high) {
    if (low < high) {
        int pi = partition(A, low, high);
        quicksort(A, low, pi - 1);
        quicksort(A, pi + 1, high);
    }
}

int main() {
    int A[] = {8, 3, 5, 1, 9, 2};
    int n = sizeof(A) / sizeof(A[0]);

    quicksort(A, 0, n - 1);

    printf("Partitioned/sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", A[i]);
    printf("\n");

    return 0;
}

Sample Input and Output

Input: Array = [8, 3, 5, 1, 9, 2]

Output:

Partitioned/sorted array: 1 2 3 5 8 9

The single partition step I traced by hand corresponds to the first level of recursion here; the full quicksort continues partitioning each side until the array is sorted.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version