Unit II — Linear Data Structures, Searching & Sorting

Syllabus Coverage: Concept of sequential organization, Arrays as ADT, Storage representation of Array, Array insertion and deletion, Matrix operations using arrays, String operations (Length, Concatenation, Copy, Palindrome, Reverse, Compare, Substring) without using library functions, Searching: Linear and Binary search algorithms and its analysis. Sorting: General concepts and algorithm analysis — Bubble sort, Insertion sort, Selection sort, Merge sort, Quick sort, Heap sort, stable and in-place sorting, sorting techniques in linear time — Counting sort. (09 Hours)

Table of Contents

Glossary — Key Terms

1 — Arrays

1.1 Sequential Organization

In sequential organization:

• Elements are stored one after another in memory
• The address of any element can be calculated directly from its index
• Random access is possible (access any element in $O(1)$ time)
• Insertion and deletion are expensive (require shifting)

The array is the most fundamental sequential data structure.

1.2 Array as an ADT

ADT Array:
    Data:
        A fixed-size, ordered collection of elements of the same type
        Each element is identified by an index (0 to n-1)
    
    Operations:
        create(size)         → Create array of given size
        get(index)           → Return element at index         — O(1)
        set(index, value)    → Set element at index to value   — O(1)
        insert(index, value) → Insert value at index (shift)   — O(n)
        delete(index)        → Delete element at index (shift) — O(n)
        search(value)        → Find index of value             — O(n)
        length()             → Return number of elements       — O(1)
        display()            → Print all elements              — O(n)
    
    Error Conditions:
        get/set/insert/delete with invalid index → "Index out of bounds"
        insert on full array → "Array overflow"

1.3 Storage Representation of Arrays

One-Dimensional Array

If an array A of $n$ elements starts at base address $B$, and each element takes $w$ bytes:

Two-Dimensional Array — Row-Major Order

Elements are stored row by row.

For array A[m][n] starting at base address $B$:

A[0][0] A[0][1] A[0][2] A[0][3] | A[1][0] A[1][1] A[1][2] A[1][3] | A[2][0] ...
2000    2004    2008    2012     | 2016    2020    2024    2028     | 2032    ...

Two-Dimensional Array — Column-Major Order

Elements are stored column by column.

General Formula — Arbitrary Lower Bounds

The formulas above assume indexing starts at 0. In many languages (FORTRAN, Pascal) and in exam problems, arrays can start from any index — including negative values.

1D Array — A[l₁ ... u₁] (lower bound $l_1$, upper bound $u_1$):

Number of elements: $n = u_1 - l_1 + 1$

2D Array — A[l₁ ... u₁][l₂ ... u₂]:

Let $R = u_1 - l_1 + 1$ (number of rows) and $C = u_2 - l_2 + 1$ (number of columns).

Row-Major:

Column-Major:

🔍 Key Insight: The simplified formulas ($B + (i \times n + j) \times w$) are just special cases where $l_1 = 0$ and $l_2 = 0$. When you substitute $l_1 = l_2 = 0$ into the general formula, the subtraction terms vanish and you get the simplified version. Always use the general formula in exams unless the problem explicitly states 0-based indexing.

1.4 Array Insertion and Deletion

Insertion at Position pos

// Insert 'value' at position 'pos' in array A of size n
void insert(int A[], int *n, int pos, int value) {
    // Step 1: Shift elements to the right
    for (int i = *n - 1; i >= pos; i--) {
        A[i + 1] = A[i];
    }
    // Step 2: Insert the new element
    A[pos] = value;
    // Step 3: Increase size
    (*n)++;
}

🔍 Line-by-Line Logic:

• int *n — We pass size as a pointer because insertion changes the array size; the caller needs to see the updated value.
• for (int i = *n - 1; i >= pos; i--) — We shift right-to-left (from the last element toward pos). Why not left-to-right? Because shifting left-to-right would overwrite elements before we move them! Starting from the end ensures each element is safely copied to i+1 before being overwritten.
• A[i + 1] = A[i] — Each element moves one position right, creating a gap at pos.
• A[pos] = value — Once the gap is created, we simply place the new value there.
• (*n)++ — Array now has one more element. The dereferenced pointer update ensures the caller sees the new size.

Time Complexity:

• Best case (insert at end): $O(1)$
• Worst case (insert at beginning): $O(n)$ — shift all elements
• Average case: $O(n)$

Deletion at Position pos

// Delete element at position 'pos' from array A of size n
void delete(int A[], int *n, int pos) {
    // Step 1: Shift elements to the left
    for (int i = pos; i < *n - 1; i++) {
        A[i] = A[i + 1];
    }
    // Step 2: Decrease size
    (*n)--;
}

🔍 Line-by-Line Logic:

• for (int i = pos; i < *n - 1; i++) — We shift left-to-right (opposite of insertion!). Why? Because we’re filling the gap at pos by pulling elements leftward. Starting from pos ensures each position gets its replacement from i+1 before i+1 is itself overwritten.
• i < *n - 1 — We stop at the second-to-last element because A[i] = A[i+1] would access out-of-bounds if i reached *n - 1.
• A[i] = A[i + 1] — Each element slides one position left, overwriting the deleted position.
• (*n)-- — Array shrinks by one. No need to clear the last position — it’s simply ignored since size decreased.
• Notice the symmetry: Insertion shifts right-to-left, deletion shifts left-to-right. This pattern prevents data loss during shifting.

Time Complexity: Same as insertion — $O(n)$ worst case.

Before: [10, 20, 30, 40, 50]    n = 5
                ↑ pos = 2

Shift:  [10, 20, __, 30, 40, 50]   (shift 30,40,50 right)
Insert: [10, 20, 25, 30, 40, 50]   n = 6

Before: [10, 20, 30, 40, 50]    n = 5
             ↑ pos = 1

Shift:  [10, 30, 40, 50, __]   (shift 30,40,50 left)
After:  [10, 30, 40, 50]       n = 4

1.5 Matrix Operations Using Arrays

Matrix Addition

void matrixAdd(int A[][MAX], int B[][MAX], int C[][MAX], int m, int n) {
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            C[i][j] = A[i][j] + B[i][j];
}
// Time: O(m × n)    Space: O(m × n)

🔍 Why This Logic: Matrix addition is element-wise — each C[i][j] depends only on A[i][j] and B[i][j] at the same position. The two nested loops simply visit every cell exactly once. Both matrices must have identical dimensions m × n.

Matrix Multiplication

For $A_{m \times p}$ and $B_{p \times n}$, result is $C_{m \times n}$:

void matrixMultiply(int A[][MAX], int B[][MAX], int C[][MAX], 
                    int m, int p, int n) {
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            C[i][j] = 0;
            for (int k = 0; k < p; k++)
                C[i][j] += A[i][k] * B[k][j];
        }
}
// Time: O(m × n × p)    For square matrices: O(n³)

🔍 Line-by-Line Logic:

• C[i][j] = 0 — We must initialize before accumulating sums. Without this, C[i][j] might hold garbage values and the += would produce wrong results.
• Why 3 nested loops? — Each C[i][j] is the dot product of row i of A and column j of B. The k loop computes this dot product: A[i][0]*B[0][j] + A[i][1]*B[1][j] + ... + A[i][p-1]*B[p-1][j].
• k < p — p is the shared dimension (columns of A = rows of B). This is why matrix multiplication requires A.cols == B.rows.
• Why A[i][k] * B[k][j]? — We walk across row i of A (varying k) and down column j of B (varying k). The shared index k links corresponding elements.

Matrix Transpose

void transpose(int A[][MAX], int B[][MAX], int m, int n) {
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            B[j][i] = A[i][j];
}
// Time: O(m × n)

🔍 Why This Logic: Transpose mirrors a matrix across its main diagonal — row i becomes column i. So element at position (i, j) moves to (j, i). That’s why B[j][i] = A[i][j]. Note: if A is m × n, then B must be n × m — the dimensions swap. We use a separate output matrix B because doing it in-place is tricky for non-square matrices.

Special Matrix Storage — Triangular, Diagonal, Symmetric & Tridiagonal

For an $n \times n$ matrix, storing all $n^2$ elements wastes memory when only a subset are non-zero. Special matrices exploit structure to store only the required elements in a compact 1D array.

1. Lower Triangular Matrix

A matrix where all elements above the main diagonal are zero: $A[i][j] = 0$ for $j > i$.

| 1  0  0  0 |
| 2  3  0  0 |
| 4  5  6  0 |
| 7  8  9 10 |

Non-zero elements: Row $i$ has $i + 1$ elements (0-indexed). Total = $\sum_{i=0}^{n-1}(i+1) = \frac{n(n+1)}{2}$

Row-Major Mapping (store row by row into 1D array):

🔍 Why? Before row $i$, there are $1 + 2 + \cdots + i = \frac{i(i+1)}{2}$ elements. Within row $i$, element at column $j$ is at offset $j$.

Column-Major Mapping (store column by column):

🔍 Why? Column $j$ in a lower triangular matrix has elements from row $j$ to row $n-1$. Before column $j$, there are $n + (n-1) + \cdots + (n-j+1) = \frac{j(2n - j + 1)}{2}$ elements… simplified to the formula above when we count the offset $i - j$ within the column.

2. Upper Triangular Matrix

A matrix where all elements below the main diagonal are zero: $A[i][j] = 0$ for $j < i$.

| 1  2  3  4 |
| 0  5  6  7 |
| 0  0  8  9 |
| 0  0  0 10 |

Non-zero elements: Row $i$ has $n - i$ elements (0-indexed). Total = $\frac{n(n+1)}{2}$

Row-Major Mapping:

🔍 Why? Before row $i$, there are $n + (n-1) + \cdots + (n-i+1) = \frac{i(2n - i + 1)}{2}$ elements… and within row $i$, the offset from the diagonal is $j - i$.

Column-Major Mapping:

🔍 Why? Column $j$ has elements from row $0$ to row $j$. Before column $j$, there are $1 + 2 + \cdots + j = \frac{j(j+1)}{2}$ elements. Within column $j$, element at row $i$ is at offset $i$.

3. Diagonal Matrix

A matrix where all elements outside the main diagonal are zero: $A[i][j] = 0$ for $i \neq j$.

| 5  0  0  0 |
| 0  3  0  0 |
| 0  0  7  0 |
| 0  0  0  2 |

Storage: Only $n$ elements needed. Mapping is trivial:

🔍 Only diagonal elements $A[0][0], A[1][1], \ldots, A[n-1][n-1]$ are stored. Any access $A[i][j]$ with $i \neq j$ returns 0 without accessing the array.

4. Symmetric Matrix

A matrix where $A[i][j] = A[j][i]$ for all $i, j$. Store only the lower triangular part (or upper) — the other half is a mirror.

Storage: Same as Lower Triangular = $\frac{n(n+1)}{2}$ elements.

5. Tridiagonal Matrix

A matrix where non-zero elements appear only on:

• Main diagonal ($i = j$)
• Diagonal above ($j = i + 1$)
• Diagonal below ($j = i - 1$)

| 1  2  0  0  0 |
| 3  4  5  0  0 |
| 0  6  7  8  0 |
| 0  0  9 10 11 |
| 0  0  0 12 13 |

Non-zero elements: $3n - 2$ (for $n \geq 2$). The first and last rows have 2 elements each; all middle rows have 3.

Mapping to 1D array (row-major):

🔍 Why $2i + j$? Row 0 contributes 2 elements (at columns 0, 1). Each subsequent row $i$ starts at position $2i$ in the 1D array (2 elements per row for prior rows, minus the offset). The column within the band is $j$, giving offset $j$.

Alternatively (3-band mapping):

1.6 Finding Minimum & Maximum — Tournament Method

Naïve Algorithm — Single Pass:

void findMinMax(int arr[], int n, int *min, int *max) {
    *min = *max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < *min) *min = arr[i];
        if (arr[i] > *max) *max = arr[i];
    }
}
// Comparisons: 2(n-1) — two comparisons per element

🔍 Why 2(n-1)? Each element (except the first) is compared against both the current min and max — that’s 2 comparisons per element for $n-1$ elements.

Tournament Method (Pairwise Comparison):

The key insight: compare pairs of elements first, then compare the smaller with min and the larger with max. This saves comparisons.

void tournamentMinMax(int arr[], int n, int *min, int *max) {
    int i;
    
    // Handle odd/even n
    if (n % 2 == 0) {
        if (arr[0] < arr[1]) { *min = arr[0]; *max = arr[1]; }
        else                 { *min = arr[1]; *max = arr[0]; }
        i = 2;  // Start from index 2
    } else {
        *min = *max = arr[0];
        i = 1;  // Start from index 1
    }
    
    // Process pairs
    for (; i < n - 1; i += 2) {
        if (arr[i] < arr[i + 1]) {
            if (arr[i] < *min)     *min = arr[i];
            if (arr[i + 1] > *max) *max = arr[i + 1];
        } else {
            if (arr[i + 1] < *min) *min = arr[i + 1];
            if (arr[i] > *max)     *max = arr[i];
        }
    }
}
// Comparisons: ⌈3n/2⌉ - 2

🔍 Line-by-Line Logic:

• Pair comparison first — Compare arr[i] with arr[i+1] (1 comparison). This tells us which is the candidate for min and which for max.
• Then compare with running min/max — The smaller of the pair only needs to be compared with min (1 comparison). The larger only with max (1 comparison).
• 3 comparisons per 2 elements — Instead of 4 comparisons per 2 elements (naïve). For $n$ elements: $\lceil 3n/2 \rceil - 2$ total.
• Odd $n$ handling — If odd, initialize min and max with the first element alone, then process remaining elements in pairs.
• Why is this optimal? — It can be proven that $\lceil 3n/2 \rceil - 2$ is the theoretical lower bound for simultaneous min-max finding. This algorithm achieves it.

Recursive Tournament (Divide & Conquer) Version:

typedef struct { int min; int max; } MinMax;

MinMax tournamentDC(int arr[], int low, int high) {
    MinMax result, left, right;
    
    if (low == high) {  // Single element
        result.min = result.max = arr[low];
        return result;
    }
    if (high == low + 1) {  // Two elements
        if (arr[low] < arr[high]) {
            result.min = arr[low]; result.max = arr[high];
        } else {
            result.min = arr[high]; result.max = arr[low];
        }
        return result;
    }
    
    int mid = (low + high) / 2;
    left = tournamentDC(arr, low, mid);
    right = tournamentDC(arr, mid + 1, high);
    
    result.min = (left.min < right.min) ? left.min : right.min;
    result.max = (left.max > right.max) ? left.max : right.max;
    return result;
}

🔍 Why “Tournament”? Think of it like a sports tournament — elements are paired off, winners (max candidates) advance up one bracket, losers (min candidates) advance up another. The overall min and max emerge from fewer total “matches” (comparisons).

Practice Questions — Arrays

2 — String Operations (Without Library Functions)

2.1 String Basics

char str[] = "Hello";
// Stored as: ['H', 'e', 'l', 'l', 'o', '\0']
// Size = 6 bytes (5 characters + 1 null terminator)

2.2 String Length

int stringLength(char str[]) {
    int len = 0;
    while (str[len] != '\0') {
        len++;
    }
    return len;
}
// Time: O(n)    Space: O(1)

🔍 Why This Logic: In C, strings have no built-in length field — the only way to know where a string ends is to find the null terminator '\0'. So we start a counter at 0 and walk forward character by character. Each time we see a non-null character, we increment. When we hit '\0', the counter holds the length. This is exactly what strlen() does internally.

2.3 String Copy

void stringCopy(char dest[], char src[]) {
    int i = 0;
    while (src[i] != '\0') {
        dest[i] = src[i];
        i++;
    }
    dest[i] = '\0';  // Don't forget the null terminator!
}
// Time: O(n)    Space: O(1) (excluding destination)

🔍 Line-by-Line Logic:

• while (src[i] != '\0') — We copy characters one-by-one until we reach the source string’s end.
• dest[i] = src[i] — Same index i for both arrays because we want a 1:1 copy.
• dest[i] = '\0' — Critical! The while loop copies data characters but stops before copying '\0'. We must manually add it, otherwise dest won’t be a valid C string and any subsequent string operation on it would read garbage past the end.

2.4 String Concatenation

void stringConcat(char dest[], char src[]) {
    int i = 0, j = 0;
    // Find end of dest
    while (dest[i] != '\0') i++;
    // Copy src to end of dest
    while (src[j] != '\0') {
        dest[i] = src[j];
        i++;
        j++;
    }
    dest[i] = '\0';
}
// Time: O(m + n) where m = len(dest), n = len(src)

🔍 Line-by-Line Logic:

• Two-phase approach: First find where dest ends (phase 1), then append src there (phase 2).
• while (dest[i] != '\0') i++; — This walks i to the null terminator position of dest. We need this because we must start writing src after the existing content.
• Separate indices i and j — i tracks position in dest (continuing from end), j tracks position in src (starting from 0). They advance independently.
• dest[i] = '\0' — Again, we must null-terminate the result. The concatenated string needs its own end marker.
• Time is O(m+n) because we traverse dest once (m steps) then src once (n steps).

2.5 String Reverse

void stringReverse(char str[]) {
    int len = 0;
    while (str[len] != '\0') len++;
    
    int start = 0, end = len - 1;
    while (start < end) {
        // Swap characters
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        start++;
        end--;
    }
}
// Time: O(n)    Space: O(1)

🔍 Line-by-Line Logic:

• Two-pointer technique: start begins at the first character, end at the last. They move toward each other, swapping characters along the way.
• while (start < end) — We stop when pointers meet/cross. If the string has odd length, the middle character stays in place (it’s its own mirror). If even, all characters get swapped.
• Why not start <= end? Because when start == end, they point to the same character — swapping it with itself is pointless.
• In-place reversal — We use only one temp variable for swapping, no extra array. This is the most space-efficient approach ($O(1)$).
• Why find length first? We need end = len - 1 to know where the last character is. Alternatively, you could walk a pointer to the end, but computing length is cleaner.

2.6 String Compare

int stringCompare(char s1[], char s2[]) {
    int i = 0;
    while (s1[i] != '\0' && s2[i] != '\0') {
        if (s1[i] < s2[i]) return -1;   // s1 < s2
        if (s1[i] > s2[i]) return 1;    // s1 > s2
        i++;
    }
    // If we reach here, one or both strings ended
    if (s1[i] == '\0' && s2[i] == '\0') return 0;   // equal
    if (s1[i] == '\0') return -1;   // s1 is shorter
    return 1;                        // s2 is shorter
}
// Time: O(min(m, n))    Space: O(1)

🔍 Line-by-Line Logic:

• Lexicographic (dictionary) comparison — We compare strings character by character, just like how words are ordered in a dictionary.
• while (s1[i] != '\0' && s2[i] != '\0') — We keep comparing as long as both strings still have characters. The && ensures we don’t read past either string’s end.
• if (s1[i] < s2[i]) return -1 — Characters are compared by ASCII values. E.g., 'a'(97) < 'b'(98), so "apple" < "banana". The moment we find a difference, the result is known — no need to check further.
• Post-loop checks — If the loop ends without finding a difference, the strings are identical up to the shorter one’s length. Then:
  • Both ended ('\0') → they’re equal (return 0)
  • s1 ended first → s1 is shorter, so s1 < s2 (e.g., "app" < "apple")
  • s2 ended first → s2 is shorter, so s1 > s2

2.7 Palindrome Check

int isPalindrome(char str[]) {
    int len = 0;
    while (str[len] != '\0') len++;
    
    int start = 0, end = len - 1;
    while (start < end) {
        if (str[start] != str[end])
            return 0;  // Not a palindrome
        start++;
        end--;
    }
    return 1;  // Is a palindrome
}
// Time: O(n)    Space: O(1)

🔍 Why This Logic:

• Same two-pointer technique as stringReverse, but instead of swapping, we compare. A palindrome reads the same forwards and backwards, so str[0] must equal str[len-1], str[1] must equal str[len-2], etc.
• Early exit on mismatch — The moment any pair doesn’t match, we immediately return 0. No need to check further pairs — one mismatch is enough to prove it’s not a palindrome.
• We only check half the string — The start < end condition means we do at most n/2 comparisons. Checking the full string would be redundant since each comparison covers both a character and its mirror.

2.8 Substring Search

Find if string pattern exists in string text:

int substringSearch(char text[], char pattern[]) {
    int n = 0, m = 0;
    while (text[n] != '\0') n++;      // length of text
    while (pattern[m] != '\0') m++;   // length of pattern
    
    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (text[i + j] != pattern[j])
                break;
        }
        if (j == m)
            return i;  // Pattern found at index i
    }
    return -1;  // Not found
}
// Time: O(n × m) worst case    Space: O(1)

🔍 Line-by-Line Logic:

• i <= n - m — We only try starting positions where the pattern can fully fit. If the text has 10 chars and pattern has 3, the last valid starting position is index 7 (positions 7, 8, 9). Starting at index 8 would go out of bounds.
• The inner j loop — For each starting position i, compare text[i+0] with pattern[0], text[i+1] with pattern[1], etc. The offset i+j maps pattern positions to text positions.
• break on mismatch — As soon as any character doesn’t match, there’s no point checking the rest of this alignment — move to next starting position.
• if (j == m) — If j made it all the way to m (pattern length) without breaking, ALL characters matched — the pattern is found at position i. If j < m, the break triggered, meaning a mismatch occurred.
• This is the “Brute Force” or “Naive” pattern matching algorithm. It’s $O(n \times m)$ in the worst case (e.g., text=”AAAAAB”, pattern=”AAB”). Faster algorithms like KMP achieve $O(n+m)$.

Practice Questions — Strings

3 — Searching

3.1 Linear Search

Algorithm

int linearSearch(int A[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (A[i] == key)
            return i;    // Found at index i
    }
    return -1;           // Not found
}

🔍 Line-by-Line Logic:

• for (int i = 0; i < n; i++) — Check every element from index 0 to n-1. There’s no shortcut because the array is unsorted — the key could be anywhere.
• if (A[i] == key) return i — Return immediately upon finding the key. We don’t need to check further because the question is “does it exist and where?” Returning the index (not just 1) gives the caller the position.
• return -1 — If the loop completes without finding the key, it’s not in the array. We use -1 as a sentinel value because valid indices are 0 to n-1, so -1 unambiguously means “not found.”
• No prerequisites — Unlike binary search, this works on unsorted, sorted, linked lists, anything. It’s the simplest search possible.

Analysis

Space Complexity: $O(1)$ — no extra space needed.

3.2 Binary Search

Algorithm (Iterative)

int binarySearch(int A[], int n, int key) {
    int low = 0, high = n - 1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;  // avoids overflow
        
        if (A[mid] == key)
            return mid;         // Found
        else if (A[mid] < key)
            low = mid + 1;     // Search right half
        else
            high = mid - 1;    // Search left half
    }
    return -1;                  // Not found
}

🔍 Line-by-Line Logic:

• low = 0, high = n - 1 — These define the search window. Initially, the entire array is our search space.
• while (low <= high) — As long as there’s at least one element to check. When low > high, the search window is empty — key doesn’t exist.
• mid = low + (high - low) / 2 — Why not (low + high) / 2? Because if low and high are both large (near INT_MAX), their sum can overflow! The formula low + (high - low)/2 gives the same result without overflow risk. This is a classic bug that even professional code had for decades.
• if (A[mid] == key) — Found it! Return the index.
• else if (A[mid] < key) → low = mid + 1 — The key is larger than the middle element. Since the array is sorted, the key must be in the right half. We set low = mid + 1 (not mid) because we’ve already checked mid and it’s not the answer.
• else → high = mid - 1 — The key is smaller, so search the left half. Again, mid - 1 because mid is ruled out.
• Each iteration halves the search space — That’s why it’s $O(\log n)$. For 1 million elements, at most 20 comparisons!

Algorithm (Recursive)

int binarySearchRec(int A[], int low, int high, int key) {
    if (low > high)
        return -1;             // Base case: not found
    
    int mid = low + (high - low) / 2;
    
    if (A[mid] == key)
        return mid;
    else if (A[mid] < key)
        return binarySearchRec(A, mid + 1, high, key);
    else
        return binarySearchRec(A, low, mid - 1, key);
}

🔍 Why Recursive Version?

• Same logic as iterative, but expressed as tail recursion — each call replaces the loop iteration.
• if (low > high) return -1 — Base case replaces the while condition. When the search window is empty, we stop.
• return binarySearchRec(A, mid + 1, high, key) — Instead of updating low = mid + 1 and looping, we make a new function call with the updated range.
• Trade-off: The recursive version uses $O(\log n)$ stack space for the call frames, while the iterative version uses $O(1)$. In practice, iterative is preferred for this reason.
• Both versions are correct — the recursive one is more “elegant” and maps directly to the mathematical definition: “search in [low, mid-1] or [mid+1, high].”

Dry Run Example

A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
     0  1  2   3   4   5   6   7   8   9

Step 1: low=0, high=9, mid=4 → A[4]=16 < 23 → low=5
Step 2: low=5, high=9, mid=7 → A[7]=56 > 23 → high=6
Step 3: low=5, high=6, mid=5 → A[5]=23 == 23 → FOUND at index 5! ✔

Analysis

Space Complexity:

• Iterative: $O(1)$
• Recursive: $O(\log n)$ — due to recursion stack

3.3 Comparison — Linear vs Binary Search

Practice Questions — Searching

4 — Sorting

4.1 Sorting Concepts — Stable & In-Place

4.2 Bubble Sort

Algorithm

void bubbleSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;  // Optimization flag
        for (int j = 0; j < n - 1 - i; j++) {
            if (A[j] > A[j + 1]) {
                // Swap
                int temp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;  // Already sorted — early exit
    }
}

🔍 Line-by-Line Logic:

• i < n - 1 — We need at most n-1 passes. Why? After each pass, the largest unsorted element reaches its final position. After n-1 passes, n-1 elements are placed, so the last one is automatically correct.
• j < n - 1 - i — This is the key optimization the user asked about! After pass i, the last i elements are already in their final sorted positions (they “bubbled up”). So we don’t need to compare them again. In pass 0, we check all n-1 pairs. In pass 1, the last element is sorted, so we check n-2 pairs. In pass i, we check n-1-i pairs. Without -i, the algorithm would still be correct but would do useless comparisons.
• if (A[j] > A[j + 1]) → swap — Compare adjacent elements. If the left one is larger, they’re in wrong order — swap them. This is what makes larger elements “bubble” rightward.
• swapped flag — If we complete an entire pass without any swaps, the array is already sorted! The break skips remaining passes. This turns best-case (already sorted) from $O(n^2)$ to $O(n)$.
• Why compare adjacent pairs? — Think of it like bubbles rising in water. Each pass pushes the biggest unsorted element to the end, one swap at a time. After pass 0: max is at position n-1. After pass 1: second-max at n-2. And so on.

Dry Run

[64, 34, 25, 12, 22, 11, 90]
 64>34 → swap → [34, 64, 25, 12, 22, 11, 90]
 64>25 → swap → [34, 25, 64, 12, 22, 11, 90]
 64>12 → swap → [34, 25, 12, 64, 22, 11, 90]
 64>22 → swap → [34, 25, 12, 22, 64, 11, 90]
 64>11 → swap → [34, 25, 12, 22, 11, 64, 90]
 64<90 → no swap
After Pass 1: [34, 25, 12, 22, 11, 64, 90]  ← 90 is in place

Analysis

Space: $O(1)$ — In-place
Stable: Yes ✔ (equal elements are never swapped)

4.3 Selection Sort

Algorithm

void selectionSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[minIdx])
                minIdx = j;
        }
        // Swap A[i] and A[minIdx]
        int temp = A[i];
        A[i] = A[minIdx];
        A[minIdx] = temp;
    }
}

🔍 Line-by-Line Logic:

• i < n - 1 — We place n-1 elements; the last one is automatically correct.
• minIdx = i — We assume the current position holds the minimum. Then we scan the rest to see if there’s something smaller.
• for (int j = i + 1; j < n; j++) — Search the unsorted portion (from i+1 to end) for the actual minimum. Why start at i+1? Because positions 0 to i-1 are already sorted from previous passes.
• if (A[j] < A[minIdx]) minIdx = j — We only update the index, not swap yet. Why? Because we want to find the true minimum first, not swap multiple times. This is what makes selection sort do exactly n-1 swaps total — one swap per pass, unlike bubble sort which may swap many times per pass.
• The swap after the inner loop — Once we know the minimum’s position, one swap puts it in place. This is why selection sort is preferred when write operations are expensive (e.g., writing to flash memory).
• Why is it unstable? — The swap can move A[i] to a distant position, jumping over equal elements. Example: [5a, 5b, 3] → swap 5a with 3 → [3, 5b, 5a] — 5a and 5b changed relative order.

Dry Run

Pass 1: Find min in [64,25,12,22,11] → 11 at idx 4. Swap with idx 0.
        [11, 25, 12, 22, 64]

Pass 2: Find min in [25,12,22,64] → 12 at idx 2. Swap with idx 1.
        [11, 12, 25, 22, 64]

Pass 3: Find min in [25,22,64] → 22 at idx 3. Swap with idx 2.
        [11, 12, 22, 25, 64]

Pass 4: Find min in [25,64] → 25 at idx 3. No swap needed.
        [11, 12, 22, 25, 64]  ✔ SORTED

Analysis

Space: $O(1)$ — In-place
Stable: No ✗ (swapping can change relative order of equal elements)

4.4 Insertion Sort

Algorithm

void insertionSort(int A[], int n) {
    for (int i = 1; i < n; i++) {
        int key = A[i];
        int j = i - 1;
        // Shift elements greater than key to the right
        while (j >= 0 && A[j] > key) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = key;
    }
}

🔍 Line-by-Line Logic:

• i = 1 — We start from the second element because a single element (index 0) is trivially sorted. The sorted portion initially is just A[0].
• key = A[i] — We save the element to be inserted. This is crucial because the shifting in the while loop will overwrite A[i].
• j = i - 1 — Start comparing from the rightmost element of the sorted portion (just left of key).
• while (j >= 0 && A[j] > key) — Two conditions:
  • j >= 0 — Don’t go past the beginning of the array (bounds check).
  • A[j] > key — Keep shifting as long as elements are larger than key. Equal elements are NOT shifted (> not >=), which is why insertion sort is stable.
• A[j + 1] = A[j] — Shift element one position right to make room. We don’t need a swap — just overwrite A[j+1] because we saved the original value in key.
• j-- — Move left to check the next element.
• A[j + 1] = key — When the while loop ends, j is either -1 (key is smallest) or A[j] <= key. Either way, j+1 is the correct insertion position.
• Think of it like sorting a hand of cards — You pick up one card at a time and slide it into the correct position among the cards you’re already holding.

Dry Run

i=1: key=11, compare with 12. 12>11 → shift. Insert 11 at pos 0.
     [11, 12, 13, 5, 6]

i=2: key=13, compare with 12. 12<13 → stop. Already in place.
     [11, 12, 13, 5, 6]

i=3: key=5, compare with 13→shift, 12→shift, 11→shift. Insert at pos 0.
     [5, 11, 12, 13, 6]

i=4: key=6, compare with 13→shift, 12→shift, 11→shift. Insert at pos 1.
     [5, 6, 11, 12, 13]  ✔ SORTED

Analysis

Space: $O(1)$ — In-place
Stable: Yes ✔

4.5 Merge Sort

Algorithm

void merge(int A[], int left, int mid, int right) {
    int n1 = mid - left + 1;   // size of left half
    int n2 = right - mid;       // size of right half
    
    // Create temp arrays
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = A[left + i];
    for (int j = 0; j < n2; j++) R[j] = A[mid + 1 + j];
    
    // Merge back into A[left..right]
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j])       // <= ensures stability
            A[k++] = L[i++];
        else
            A[k++] = R[j++];
    }
    // Copy remaining elements
    while (i < n1) A[k++] = L[i++];
    while (j < n2) A[k++] = R[j++];
}

void mergeSort(int A[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(A, left, mid);        // Sort left half
        mergeSort(A, mid + 1, right);   // Sort right half
        merge(A, left, mid, right);     // Merge sorted halves
    }
}

🔍 Line-by-Line Logic — merge():

• n1 = mid - left + 1 — Size of left half [left..mid]. The +1 is because both endpoints are inclusive.
• n2 = right - mid — Size of right half [mid+1..right]. No +1 needed because right - (mid+1) + 1 = right - mid.
• Why create temp arrays L[] and R[]? — We’re about to overwrite A[left..right] during merging. If we didn’t copy the data first, we’d lose the original values. This is why merge sort needs $O(n)$ extra space.
• if (L[i] <= R[j]) — The <= is critical for stability! When elements are equal, we pick from the left array first. Since left-array elements appeared first in the original array, their relative order is preserved. Using < instead would make it unstable.
• The main while loop — Two-pointer merge: compare the front elements of both halves, take the smaller one. This works because both halves are already sorted (guaranteed by recursion). Think of merging two sorted decks of cards.
• Remaining-element loops — One array might run out before the other. The remaining elements are already sorted and all larger than what’s been placed, so just copy them directly.

Line-by-Line Logic — mergeSort():

• if (left < right) — Base case: if left >= right, the sub-array has 0 or 1 element, which is inherently sorted. No work needed.
• mid = left + (right - left) / 2 — Same overflow-safe midpoint formula as binary search.
• Divide → Conquer → Combine — First sort left half, then right half, then merge them. The recursion goes deeper and deeper until we hit single elements, then merges build the sorted result bottom-up.

Dry Run

                    [38, 27, 43, 3, 9, 82, 10]
                   /                           \
          [38, 27, 43, 3]              [9, 82, 10]
          /             \              /          \
      [38, 27]      [43, 3]       [9, 82]      [10]
      /     \       /    \        /     \         |
    [38]  [27]   [43]   [3]    [9]   [82]      [10]
      \    /       \    /        \    /           |
     [27, 38]    [3, 43]       [9, 82]         [10]
         \          /              \            /
      [3, 27, 38, 43]          [9, 10, 82]
              \                    /
        [3, 9, 10, 27, 38, 43, 82]  ✔ SORTED

Analysis

Recurrence: $T(n) = 2T(n/2) + O(n)$ → By Master Theorem: $O(n \log n)$

Space: $O(n)$ — needs auxiliary arrays for merging
Stable: Yes ✔
In-Place: No ✗ (needs $O(n)$ extra space)

4.6 Quick Sort

Algorithm (Lomuto Partition Scheme)

int partition(int A[], int low, int high) {
    int pivot = A[high];  // Choose last element as pivot
    int i = low - 1;      // Index of smaller element
    
    for (int j = low; j < high; j++) {
        if (A[j] <= pivot) {
            i++;
            // Swap A[i] and A[j]
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
    // Place pivot in correct position
    int temp = A[i + 1];
    A[i + 1] = A[high];
    A[high] = temp;
    
    return i + 1;  // Return pivot index
}

void quickSort(int A[], int low, int high) {
    if (low < high) {
        int pi = partition(A, low, high);
        quickSort(A, low, pi - 1);    // Sort left of pivot
        quickSort(A, pi + 1, high);   // Sort right of pivot
    }
}

🔍 Line-by-Line Logic — partition() (Lomuto Scheme):

• pivot = A[high] — We choose the last element as pivot. Other strategies (first, random, median-of-three) exist, but last-element is simplest to implement.
• i = low - 1 — i tracks the boundary between “≤ pivot” elements and “> pivot” elements. It starts before low because no elements have been classified yet. Everything to the left of i (inclusive) is ≤ pivot.
• for (int j = low; j < high; j++) — j scans through all elements (except pivot itself). For each element, we decide: is it ≤ pivot or > pivot?
• if (A[j] <= pivot) { i++; swap(A[i], A[j]); } — Found an element that belongs in the “small” section. Increment i to extend the small section, then swap A[j] into position i. Elements between i+1 and j-1 are all > pivot.
• Final swap: A[i+1] ↔ A[high] — Place the pivot between the two partitions. Position i+1 is the first element > pivot, so swapping puts pivot at the exact boundary. Everything left is ≤ pivot, everything right is > pivot.
• return i + 1 — The pivot’s final index. It will never move again.

Why Lomuto over Hoare? Lomuto is easier to understand and implement. Hoare’s partition is slightly more efficient (fewer swaps on average) but harder to code correctly.

Why worst case is $O(n^2)$: If array is already sorted and we pick the last element as pivot, the pivot is always the largest. Every partition produces sub-arrays of size n-1 and 0. That gives $T(n) = T(n-1) + O(n) = O(n^2)$.

Dry Run

Partition around pivot 70:
  Elements ≤ 70: [10, 30, 40, 50]
  Pivot: [70]
  Elements > 70: [80, 90]
  
  Result: [10, 30, 40, 50, 70, 80, 90]
                            ↑
                     Pivot in final position

Recursively sort [10, 30, 40, 50] and [80, 90]
→ [10, 30, 40, 50, 70, 80, 90]  ✔ SORTED

Analysis

Space: $O(\log n)$ average (recursion stack), $O(n)$ worst case
Stable: No ✗
In-Place: Yes ✔ (with recursion stack overhead)

4.7 Heap Sort

Heap Basics (Array Representation)

For a node at index $i$ (0-indexed):

• Left child: $2i + 1$
• Right child: $2i + 2$
• Parent: $\lfloor(i - 1) / 2\rfloor$

Algorithm

void heapify(int A[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && A[left] > A[largest])
        largest = left;
    if (right < n && A[right] > A[largest])
        largest = right;
    
    if (largest != i) {
        int temp = A[i];
        A[i] = A[largest];
        A[largest] = temp;
        heapify(A, n, largest);  // Recursively fix subtree
    }
}

void heapSort(int A[], int n) {
    // Step 1: Build Max-Heap (from last non-leaf to root)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(A, n, i);
    
    // Step 2: Extract max one by one
    for (int i = n - 1; i > 0; i--) {
        // Move current root (max) to end
        int temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        // Heapify reduced heap
        heapify(A, i, 0);
    }
}

🔍 Line-by-Line Logic — heapify():

• largest = i — Assume the current node is the largest among itself and its children.
• left = 2*i + 1, right = 2*i + 2 — These formulas come from the array representation of a complete binary tree. For 0-indexed arrays, the children of node i are at 2i+1 and 2i+2.
• if (left < n && A[left] > A[largest]) — Two checks: (1) does the left child exist? (left < n), and (2) is it larger than the current largest? The bounds check prevents array out-of-bounds.
• if (largest != i) → swap and recurse — If a child was larger, swap parent with that child to fix the violation. But now the child’s subtree might be violated, so we recursively heapify downward. This “sifting down” continues until the element finds its correct position.

Line-by-Line Logic — heapSort():

• for (int i = n/2 - 1; i >= 0; i--) — Why start at n/2 - 1? Because nodes at indices n/2 to n-1 are leaf nodes — they have no children, so they trivially satisfy the heap property. We only need to heapify internal nodes. Starting from the last non-leaf and working up ensures that when we heapify node i, its subtrees are already valid heaps.
• Building the heap is $O(n)$, not $O(n \log n)$! — This is a counter-intuitive result. Most nodes are near the bottom (leaves) and need little work. A mathematical proof shows the total work is $O(n)$.
• A[0] ↔ A[i] — The root (maximum element) is swapped to position i (end of unsorted portion). Now A[i] is in its final position.
• heapify(A, i, 0) — The element swapped to root likely violates the heap property. Heapify fixes it. We pass i as the size (not n) because elements after index i are already sorted and excluded from the heap.
• Why is it $O(n \log n)$? — Building heap is $O(n)$, but extracting n elements costs $O(\log n)$ each = $O(n \log n)$ total.

Analysis

Building the heap: $O(n)$
$n$ extractions × heapify: $O(n \log n)$

Space: $O(1)$ — In-place ✔
Stable: No ✗

4.8 Counting Sort (Linear Time)

Algorithm

void countingSort(int A[], int n, int k) {
    int count[k + 1];  // count array for values 0 to k
    int output[n];
    
    // Initialize count array
    for (int i = 0; i <= k; i++) count[i] = 0;
    
    // Count occurrences
    for (int i = 0; i < n; i++) count[A[i]]++;
    
    // Cumulative count (prefix sum)
    for (int i = 1; i <= k; i++) count[i] += count[i - 1];
    
    // Build output array (traverse input in reverse for stability)
    for (int i = n - 1; i >= 0; i--) {
        output[count[A[i]] - 1] = A[i];
        count[A[i]]--;
    }
    
    // Copy output back to A
    for (int i = 0; i < n; i++) A[i] = output[i];
}

🔍 Line-by-Line Logic:

• int count[k + 1] — We need one counter for each possible value from 0 to k. If max value is 8, we need indices 0–8 = 9 slots.
• Phase 1 — Count occurrences: count[A[i]]++ tallies how many times each value appears. After this, count[v] = number of elements equal to v.
• Phase 2 — Cumulative count (prefix sum): count[i] += count[i - 1] transforms the count array so that count[v] now tells us how many elements are ≤ v. This directly gives us the position where value v should end up in the sorted output.
• Phase 3 — Build output (right-to-left):
  • for (int i = n - 1; i >= 0; i--) — Why traverse in reverse? This is the key to stability! When two elements have the same value, the one appearing later in the input (higher index) gets placed at a later position in the output. If we went left-to-right, equal elements would end up in reversed order.
  • output[count[A[i]] - 1] = A[i] — count[A[i]] tells us how many elements are ≤ A[i]. So position count[A[i]] - 1 (0-indexed) is where this element belongs.
  • count[A[i]]-- — Decrement so the next element with the same value goes one position earlier.
• This is NOT a comparison-based sort — It never compares two elements against each other. That’s how it beats the $\Omega(n \log n)$ lower bound for comparison sorts. The trade-off is it only works for integers in a known range.

Dry Run

Count:       [0, 1, 2, 2, 1, 0, 0, 0, 1]   (idx 0-8)
Cumulative:  [0, 1, 3, 5, 6, 6, 6, 6, 7]

Build output (right to left for stability):
  A[6]=1 → output[0]=1, count[1]=0
  A[5]=3 → output[4]=3, count[3]=4
  A[4]=3 → output[3]=3, count[3]=3
  A[3]=8 → output[6]=8, count[8]=6
  A[2]=2 → output[2]=2, count[2]=2
  A[1]=2 → output[1]=2, count[2]=1
  A[0]=4 → output[5]=4, count[4]=5

Output: [1, 2, 2, 3, 3, 4, 8]  ✔ SORTED

Analysis

4.9 Sorting Algorithms — Master Comparison

Practice Questions — Sorting

Comprehensive Unit II Practice Set

📝 View Complete Solutions for Unit II →

← Back to DSA Index