Decrease by Constant & Combinatorial Objects

Decrease-and-Conquer by a Constant and Combinatorial Generation

Decrease-and-conquer exploits the relationship between a solution to a given instance of size $n$ and a solution to a smaller instance of size $n - 1$ (decrease-by-a-constant, typically by 1).

Diagram loads as you scroll.

---

1. Insertion Sort

Insertion Sort sorts an array by iteratively inserting the next unsorted element into its proper position among the previously sorted elements:

InsertionSort(A[0..n-1]):
    for i = 1 to n - 1 do:
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v do:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = v

Efficiency Analysis

• Worst Case: When the array is in reverse sorted order.

$$C_{\text{worst}}(n) = \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} \in \Theta(n^2)$$

• Best Case: When the array is already sorted. Only 1 comparison is made per iteration ($A[i-1] \le v$), with 0 shifts:

$$C_{\text{best}}(n) = \sum_{i=1}^{n-1} 1 = n - 1 \in \Theta(n)$$

• Average Case: On average, half the sorted elements are examined: $\approx \frac{n^2}{4} \in \Theta(n^2)$.
• Stability: Stable. Excellent for small or nearly-sorted arrays.

---

2. Topological Sorting

A topological sort of a Directed Acyclic Graph (DAG) is a linear ordering of its vertices such that for every directed edge $(u, v)$, vertex $u$ comes before $v$ in the ordering.

Method 1: DFS-Based Method (Reverse Postorder)

1. Run Depth-First Search (DFS) on the DAG.
2. Note the order in which vertices are popped off the traversal stack (traversal completion/dead ends).
3. Reversing this order yields a valid topological sort.

• Time Complexity: $\Theta(|V| + |E|)$.

Method 2: Source-Removal Method

1. Identify a source vertex (a vertex with in-degree 0).
2. Delete that source vertex and all its outgoing edges from the graph.
3. Append the deleted vertex to the topological order.
4. Repeat until all vertices are removed (or if no source exists, a cycle is detected).

• Time Complexity: $\Theta(|V| + |E|)$.

---

3. Algorithms for Generating Combinatorial Objects

Generating Permutations: The Johnson-Trotter Algorithm

The Johnson-Trotter algorithm generates all $n!$ permutations of $\{1, 2, \dots, n\}$ such that each subsequent permutation is obtained from the previous one by swapping a single pair of adjacent elements (minimal-change requirement).

Rules

1. Assign each integer $1, \dots, n$ an arrow indicating its direction: left ($\leftarrow$) or right ($\rightarrow$).
2. Initially, set all directions pointing left:

$$\leftarrow 1 \ \leftarrow 2 \ \leftarrow 3 \ \dots \ \leftarrow n$$

3. An element $k$ is called mobile if its arrow points to an immediately adjacent neighbor with a strictly smaller value.
4. Step:
   • Find the largest mobile integer $m$.
   • Swap $m$ with the neighbor it points to.
   • Reverse the directions of all elements strictly greater than $m$ ($k > m$).
   • Repeat until no mobile elements remain.

Visual Trace for $n = 3$ ($3! = 6$ Permutations)

Step	State	Largest Mobile Element	Action
1	$\leftarrow 1 \ \leftarrow 2 \ \leftarrow 3$	3 (points to 2)	Swap 3 and 2
2	$\leftarrow 1 \ \leftarrow 3 \ \leftarrow 2$	3 (points to 1)	Swap 3 and 1
3	$\leftarrow 3 \ \leftarrow 1 \ \leftarrow 2$	2 (3 is not mobile; 2 points to 1)	Swap 2 and 1; reverse direction of $3 > 2 \implies \rightarrow 3$
4	$\rightarrow 3 \ \leftarrow 2 \ \leftarrow 1$	3 (points to 2)	Swap 3 and 2
5	$\leftarrow 2 \ \rightarrow 3 \ \leftarrow 1$	3 (points to 1)	Swap 3 and 1
6	$\leftarrow 2 \ \leftarrow 1 \ \rightarrow 3$	None mobile!	Algorithm terminates (6 permutations generated)

---

Generating Subsets: Binary Reflected Gray Code

A Gray code lists all $2^n$ subsets of an $n$-element set such that each subset differs from its predecessor by the inclusion or exclusion of exactly one item.

Recursive definition:

• $G_1 = [0, 1]$
• For $n > 1$, prefix $G_{n-1}$ with 0, reverse $G_{n-1}$ and prefix with 1, then concatenate:

$$G_2 = [00, 01, 11, 10]$$ $$G_3 = [000, 001, 011, 010, 110, 111, 101, 100]$$

---

Exercises

Exercise 1

Apply the Johnson-Trotter algorithm from state $\leftarrow 2 \ \leftarrow 4 \ \leftarrow 3 \ \leftarrow 1$. Identify all mobile elements, the largest mobile element, and the next permutation.

Show solution ↓Hide solution ↑

Solution

Examine each element:

• 1: Points left to 3 ($1 < 3$), not mobile.
• 3: Points left to 4 ($3 < 4$), not mobile.
• 4: Points left to 2 ($4 > 2$), mobile!
• 2: Points left out of bounds, not mobile.

Largest mobile element: 4.

• Swap 4 with 2 $\implies \leftarrow 4 \ \leftarrow 2 \ \leftarrow 3 \ \leftarrow 1$.
• Reverse directions of all elements $> 4$: None exist.

Resulting state: $\leftarrow 4 \ \leftarrow 2 \ \leftarrow 3 \ \leftarrow 1$.

Exercise 2

Why does Insertion Sort outperform Bubble Sort on partially sorted data with $k$ inversions?

Show solution ↓Hide solution ↑

Solution

The number of key comparisons in Insertion Sort is bounded by $n - 1 + k$, where $k$ is the number of inversions. When an array is nearly sorted ($k = O(n)$), Insertion Sort executes in linear time $\Theta(n)$. Bubble Sort still requires full scans and multiple adjacent swaps, incurring substantial branch and memory overhead.