Sorting and String Matching (1D & 2D)

Brute Force: Sorting and String Matching

Brute force is a straightforward approach to solving a problem, usually directly based on the problem statement and definitions of the concepts involved.

1. Brute-Force Sorting Algorithms

Selection Sort

Scan the array to find its smallest element and exchange it with the first element. Then find the smallest element among the remaining $n - 1$ elements and exchange it with the second element, continuing until $n - 1$ elements are placed:

SelectionSort(A[0..n-1]):
    for i = 0 to n - 2 do:
        min_idx = i
        for j = i + 1 to n - 1 do:
            if A[j] < A[min_idx] then:
                min_idx = j
        swap(A[i], A[min_idx])

Comparisons: Independent of initial array order:

C(n) = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \sum_{i=0}^{n-2} (n - 1 - i) = \frac{(n-1)n}{2} = \Theta(n^2)

Key Swaps: $\Theta(n)$ swaps in all cases (very few writes!).
Stability: Not stable in its standard swap form.

Bubble Sort

Compare adjacent elements of the list and exchange them if they are out of order. By doing so repeatedly, the largest element “bubbles up” to the last position on each pass:

BubbleSort(A[0..n-1]):
    for i = 0 to n - 2 do:
        for j = 0 to n - 2 - i do:
            if A[j+1] < A[j] then:
                swap(A[j], A[j+1])

Step through a pass to see where the comparisons go. The highlighted line is the one currently executing, and the dimmed cells on the right are already in their final positions:

Bubble sortStep with the slider or ← →

1BubbleSort(A[0..n-1]):2    for i = 0 to n - 2 do:3        for j = 0 to n - 2 - i do:4            if A[j+1] < A[j] then:5                swap(A[j], A[j+1])

51428

Start: 5 unsorted values. Each pass bubbles the largest remaining value to the right.

1 / 34

Comparisons:

C(n) = \sum_{i=0}^{n-2} (n - 1 - i) = \frac{(n-1)n}{2} = \Theta(n^2)

Swaps: Worst case $\frac{n(n-1)}{2} = \Theta(n^2)$ swaps (when reversed).
Stability: Stable.

2. Brute-Force String Matching

1D Text Pattern Matching

Given a text $T[0..n-1]$ of length $n$ and a pattern $P[0..m-1]$ of length $m \le n$ , find the first index $i$ in $T$ where $P$ aligns completely.

BruteForceStringMatch(T[0..n-1], P[0..m-1]):
    n = length(T)
    m = length(P)
    for i = 0 to n - m do:
        j = 0
        while j < m and T[i + j] == P[j] do:
            j = j + 1
        if j == m return i
    return -1

Searching for $P = \text{"NOT"}$ inside $T = \text{"NOBODY\_NOTICED"}$ . The pattern slides one position right after each failure, and each alignment compares left to right until a character disagrees:

Pattern P = N O T slides across the text T, one shift per row.

NOBODY_NOTICED
↑i
i = 0: N and O match, then T ≠ B. Two comparisons wasted, shift right.
NOBODY_NOTICED
↑i
i = 1: N ≠ O immediately. Only one comparison before the shift.
NOBODY_NOTICED
↑i
i = 2…6 all fail on the very first character, as does i = 6 (N ≠ _).
NOBODY_NOTICED
↑i
i = 7: all three characters match — return index 7.

Worst-Case Complexity: Occurs when almost all characters match until the last one (e.g., $T = \text{"AAAAAAAAAB"}$ , $P = \text{"AAB"}$ ):

C_{\text{worst}}(n, m) = m(n - m + 1) \in \Theta(nm)

Best-Case Complexity: Occurs when the very first character mismatches:

C_{\text{best}}(n, m) = n - m + 1 \in \Theta(n)

Auxiliary Space: $\Theta(1)$ .

3. 2D Board Pattern Matching

Consider a 2-dimensional character board $D$ with $R$ rows and $C$ columns. We wish to search for a 1D pattern $P$ of length $m$ appearing either horizontally (left-to-right) or vertically (top-to-bottom).

Search2DBoard(D, R, C, P, m):
    for row = 0 to R - 1 do:
        for col = 0 to C - 1 do:

            // 1. Check Horizontal (Left-to-Right)
            if col + m <= C then:
                j = 0
                while j < m and D[row][col + j] == P[j] do:
                    j = j + 1
                if j == m then:
                    output "Found horizontally at (row, col)"

            // 2. Check Vertical (Top-to-Bottom)
            if row + m <= R then:
                j = 0
                while j < m and D[row + j][col] == P[j] do:
                    j = j + 1
                if j == m then:
                    output "Found vertically at (row, col)"

Time Complexity Analysis

Total starting cells checked: $R \times C$ .
At each cell, checking horizontal takes at most $m$ character comparisons.
Checking vertical takes at most $m$ character comparisons.
Total worst-case comparisons:

2 \times (R \times C) \times m = \Theta(R \cdot C \cdot m)

For a square $n \times n$ board ( $R = C = n$ ), the complexity is:

\Theta(n^2 \cdot m)

Exercises

Exercise 1

Tracing 1D Brute Force String Match: How many character comparisons are made searching for pattern $P = \text{"BAA"}$ in text $T = \text{"AABAAA"}$ ?

Show solution ↓

Solution

$T = \text{"AABAAA"}$ ( $n=6$ ), $P = \text{"BAA"}$ ( $m=3$ ). Number of alignments: $n - m + 1 = 4$ (indices $i = 0, 1, 2, 3$ ).

$i = 0$ ( $T[0..2] = \text{"AAB"}$ ): $T[0] = \text{'A'} \ne P[0] = \text{'B'}$ . (1 comparison, mismatch).
$i = 1$ ( $T[1..3] = \text{"ABA"}$ ): $T[1] = \text{'A'} \ne P[0] = \text{'B'}$ . (1 comparison, mismatch).
$i = 2$ ( $T[2..4] = \text{"BAA"}$ ): $T[2] = \text{'B'} == P[0] = \text{'B'}$ (match 1) $T[3] = \text{'A'} == P[1] = \text{'A'}$ (match 2) $T[4] = \text{'A'} == P[2] = \text{'A'}$ (match 3) Match found at index 2! (3 comparisons).

Total comparisons made: $1 + 1 + 3 = 5$ character comparisons.

Exercise 2

Why is Bubble Sort generally slower than Selection Sort in practice, despite both performing $\frac{n(n-1)}{2}$ comparisons in their standard versions?

Show solution ↓

Solution

Although both have identical comparison counts $\Theta(n^2)$ :

Selection Sort executes at most $n - 1$ swaps across the entire sort (one per outer iteration).
Bubble Sort performs swaps within the inner loop on every out-of-order adjacent pair, executing up to $\frac{n(n-1)}{2} = \Theta(n^2)$ memory writes.

Because memory writes are significantly more expensive than register comparisons, Bubble Sort runs substantially slower.