← C

Sorting & Searching

← Sorting & Searching

Select a question from the sidebar

15 questions in this topic

Question 1 / 15

How do you implement bubble sort in C and what optimizations can be applied?

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Each pass "bubbles" the largest unsorted element to its correct position.

Basic version: Two nested loops, O(n^2) always.

Optimization 1 -- Early termination: If no swaps occur in a pass, the array is already sorted. Add a swapped flag. Best case becomes O(n) for nearly sorted data.

Optimization 2 -- Shrinking range: After each pass, the last element is in place. Reduce the inner loop range by 1 each pass.

Time: O(n^2) worst/average, O(n) best (with flag). Space: O(1). Stable: Yes (equal elements maintain relative order).

Pseudo Code

BubbleSort(arr, n):
  for i = 0 to n-2:
    swapped = false
    for j = 0 to n-2-i:
      if arr[j] > arr[j+1]:
        swap(arr[j], arr[j+1])
        swapped = true
    if not swapped: break  // already sorted

Code

#include <stdio.h>

/* Optimized bubble sort with early termination */
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                /* Swap */
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;  /* array is sorted */
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main(void) {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Before: ");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("After:  ");
    printArray(arr, n);  /* 11 12 22 25 34 64 90 */

    return 0;
}

Before: 64 34 25 12 22 11 90 
After:  11 12 22 25 34 64 90

Key Points

•Repeatedly swap adjacent out-of-order elements
•O(n^2) worst/average, O(n) best with early termination flag
•Stable sort: equal elements keep their original order
•O(1) space -- in-place sorting
•Inner loop range shrinks by 1 each pass (last i elements are sorted)

Gotchas

•Without the swapped flag, bubble sort is always O(n^2) even for sorted input
•Bubble sort is almost never used in production -- it is the slowest O(n^2) sort in practice
•n-1-i in inner loop: forgetting -i means extra unnecessary comparisons
•Confusing bubble sort with selection sort -- bubble sort swaps adjacent, selection finds minimum

Compare and swap adjacent elements. Each pass bubbles the largest to the end. Add a swapped flag for O(n) best case. O(n^2) worst, stable, in-place.

•O(n^2) worst, O(n) best with flag, stable, in-place

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int t = arr[j]; arr[j] = arr[j+1]; arr[j+1] = t;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

Without swapped flag, always O(n^2) even on sorted input

Question 2 / 15

How do you implement selection sort in C?

Selection sort divides the array into sorted (left) and unsorted (right) portions. In each pass, it finds the minimum element in the unsorted portion and swaps it with the first unsorted element.

Algorithm:

For i from 0 to n-2:
Find the index of the minimum element in arr[i..n-1]
Swap arr[i] with arr[minIndex]

Time: O(n^2) always (no early termination possible). Space: O(1). Stable? No -- swapping can change the relative order of equal elements.

Advantage: Minimizes the number of swaps (exactly n-1 swaps). Good when writes are expensive (e.g., flash memory).

Pseudo Code

SelectionSort(arr, n):
  for i = 0 to n-2:
    minIdx = i
    for j = i+1 to n-1:
      if arr[j] < arr[minIdx]:
        minIdx = j
    swap(arr[i], arr[minIdx])

Code

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx])
                minIdx = j;
        }
        /* Swap only if minimum is not already in place */
        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main(void) {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Before: ");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("After:  ");
    printArray(arr, n);  /* 11 12 22 25 64 */

    return 0;
}

Before: 64 25 12 22 11 
After:  11 12 22 25 64

Key Points

•Find minimum in unsorted portion, swap with first unsorted element
•O(n^2) always -- no best case optimization
•Exactly n-1 swaps -- minimum number of writes
•NOT stable: swapping disrupts relative order of equal elements
•Simple to implement, useful when swap cost is high

Gotchas

•Always O(n^2) even on sorted input -- no early termination
•Not stable: can change relative order of equal elements
•Swapping arr[i] with itself when minIdx == i is harmless but wasteful
•Often confused with insertion sort -- selection finds min, insertion shifts elements

Find minimum in unsorted portion, swap to front. Always O(n^2), not stable, but only n-1 swaps total. In-place.

•Always O(n^2), not stable, minimal swaps

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[min]) min = j;
        if (min != i) {
            int t = arr[i]; arr[i] = arr[min]; arr[min] = t;
        }
    }
}

No early termination -- always does n^2/2 comparisons

Question 3 / 15

How do you implement insertion sort in C?

Insertion sort builds the sorted array one element at a time by inserting each element into its correct position in the already-sorted portion.

Algorithm:

Start from index 1 (index 0 is trivially sorted)
Take the current element (key)
Shift all larger elements in the sorted portion one position right
Insert key into the correct position

Time: O(n^2) worst/average, O(n) best (already sorted). Space: O(1). Stable: Yes.

Best for: Small arrays (n < ~50), nearly sorted data, online sorting (can sort as data arrives). Often used as the base case in hybrid sorts (e.g., Timsort, introsort).

Pseudo Code

InsertionSort(arr, n):
  for i = 1 to n-1:
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
      arr[j+1] = arr[j]  // shift right
      j--
    arr[j+1] = key  // insert

Code

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        /* Shift elements greater than key to the right */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;  /* insert key at correct position */
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main(void) {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Before: ");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("After:  ");
    printArray(arr, n);  /* 5 6 11 12 13 */

    /* Best case: already sorted */
    int sorted[] = {1, 2, 3, 4, 5};
    insertionSort(sorted, 5);  /* O(n) -- inner loop never executes */

    return 0;
}

Before: 12 11 13 5 6 
After:  5 6 11 12 13

Key Points

•Shift elements right to make room, then insert key
•O(n) best case (sorted input), O(n^2) worst case (reverse sorted)
•Stable sort: equal elements keep original order (uses > not >=)
•Adaptive: performance improves on nearly sorted data
•Preferred for small arrays and as base case in hybrid sorts

Gotchas

•Using >= instead of > in the comparison makes it unstable
•Starting loop at i=0 instead of i=1 causes unnecessary work
•Must save arr[i] in key before shifting -- shifting overwrites arr[i]
•O(n^2) on reverse-sorted input -- every element shifts to position 0

Take each element, shift larger elements right, insert at correct position. O(n) best (sorted), O(n^2) worst. Stable, in-place, adaptive.

•O(n) best, O(n^2) worst, stable, adaptive

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

Must save arr[i] as key before shifting -- shifting overwrites it

Question 4 / 15

How do you implement merge sort in C with a recursive approach?

Merge sort is a divide-and-conquer algorithm:

Divide: Split the array into two halves
Conquer: Recursively sort each half
Combine: Merge the two sorted halves

The merge step is the key: use two pointers to scan both halves, always picking the smaller element.

Time: O(n log n) always (worst, average, best). Space: O(n) for the auxiliary array. Stable: Yes. Not in-place: Requires O(n) extra memory.

Merge sort is optimal for linked lists (no random access needed) and is the basis for external sorting (sorting data too large for RAM).

Pseudo Code

MergeSort(arr, left, right):
  if left >= right: return
  mid = (left + right) / 2
  MergeSort(arr, left, mid)
  MergeSort(arr, mid+1, right)
  Merge(arr, left, mid, right)

Merge(arr, left, mid, right):
  Create temp arrays L[] and R[]
  Copy arr[left..mid] to L[]
  Copy arr[mid+1..right] to R[]
  Merge L[] and R[] back into arr[left..right]

Code

#include <stdio.h>
#include <stdlib.h>

/* Merge two sorted subarrays: arr[left..mid] and arr[mid+1..right] */
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    /* Allocate temp arrays */
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    /* Copy data */
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    /* Merge back */
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j])     /* <= ensures stability */
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }

    /* Copy remaining elements */
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    free(L);
    free(R);
}

void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;  /* avoid overflow */
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main(void) {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Before: ");
    printArray(arr, n);

    mergeSort(arr, 0, n - 1);

    printf("After:  ");
    printArray(arr, n);  /* 3 9 10 27 38 43 82 */

    return 0;
}

Before: 38 27 43 3 9 82 10 
After:  3 9 10 27 38 43 82

Key Points

•Divide and conquer: split, sort halves, merge
•O(n log n) guaranteed -- same for worst, average, best
•Stable sort: uses <= in merge to preserve relative order
•O(n) extra space for auxiliary arrays
•mid = left + (right - left) / 2 avoids integer overflow

Gotchas

•Using (left + right) / 2 for mid can overflow for large indices -- use left + (right - left) / 2
•Forgetting to free temp arrays causes memory leak (especially in recursive calls)
•Using < instead of <= in merge makes it unstable
•O(n) extra space is a significant disadvantage for memory-constrained systems

Divide in half, recursively sort each half, merge. Always O(n log n). Stable. Requires O(n) extra space for merge.

•Always O(n log n), stable, O(n) extra space

void merge(int a[], int l, int m, int r) {
    int n1 = m-l+1, n2 = r-m;
    int L[n1], R[n2];  /* VLA */
    for (int i=0;i<n1;i++) L[i]=a[l+i];
    for (int j=0;j<n2;j++) R[j]=a[m+1+j];
    int i=0,j=0,k=l;
    while (i<n1 && j<n2) a[k++] = L[i]<=R[j] ? L[i++] : R[j++];
    while (i<n1) a[k++]=L[i++];
    while (j<n2) a[k++]=R[j++];
}
void mergeSort(int a[], int l, int r) {
    if (l>=r) return;
    int m = l+(r-l)/2;
    mergeSort(a,l,m); mergeSort(a,m+1,r);
    merge(a,l,m,r);
}

VLAs may cause stack overflow for large arrays -- prefer malloc

Question 5 / 15

How do you implement quicksort with Lomuto and Hoare partition schemes?

Quicksort picks a pivot, partitions the array so elements less than pivot are on the left and greater on the right, then recursively sorts both sides.

Lomuto partition (simpler, slower):

Pivot = last element
Maintain index i for boundary of "less than pivot" region
Scan j from left to right, swap smaller elements to the left side
Final swap places pivot at boundary

Hoare partition (original, faster):

Pivot = first element (or median)
Two pointers start at opposite ends, move inward
Swap when left finds element >= pivot and right finds element <= pivot
Fewer swaps on average (3x fewer than Lomuto)

Time: O(n log n) average, O(n^2) worst (already sorted with bad pivot). Space: O(log n) average (stack). Not stable.

Pivot choice matters: Random pivot or median-of-three avoids worst case on sorted input.

Pseudo Code

Lomuto Partition(arr, low, high):
  pivot = arr[high]
  i = low - 1
  for j = low to high-1:
    if arr[j] <= pivot:
      i++
      swap(arr[i], arr[j])
  swap(arr[i+1], arr[high])
  return i+1

Hoare Partition(arr, low, high):
  pivot = arr[low]
  i = low - 1, j = high + 1
  while true:
    do i++ while arr[i] < pivot
    do j-- while arr[j] > pivot
    if i >= j: return j
    swap(arr[i], arr[j])

Code

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

/* Lomuto partition: pivot = last element */
int lomutoPartition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

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

void quicksortLomuto(int arr[], int low, int high) {
    if (low < high) {
        int pi = lomutoPartition(arr, low, high);
        quicksortLomuto(arr, low, pi - 1);
        quicksortLomuto(arr, pi + 1, high);
    }
}

/* Hoare partition: pivot = first element */
int hoarePartition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = low - 1;
    int j = high + 1;

    while (1) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        swap(&arr[i], &arr[j]);
    }
}

void quicksortHoare(int arr[], int low, int high) {
    if (low < high) {
        int p = hoarePartition(arr, low, high);
        quicksortHoare(arr, low, p);
        quicksortHoare(arr, p + 1, high);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main(void) {
    int arr1[] = {10, 7, 8, 9, 1, 5};
    int n = 6;
    quicksortLomuto(arr1, 0, n - 1);
    printf("Lomuto: ");
    printArray(arr1, n);  /* 1 5 7 8 9 10 */

    int arr2[] = {10, 7, 8, 9, 1, 5};
    quicksortHoare(arr2, 0, n - 1);
    printf("Hoare:  ");
    printArray(arr2, n);  /* 1 5 7 8 9 10 */

    return 0;
}

Lomuto: 1 5 7 8 9 10 
Hoare:  1 5 7 8 9 10

Key Points

•Lomuto: simpler, pivot at end, i tracks boundary of small elements
•Hoare: two pointers from ends, fewer swaps (~3x fewer), faster in practice
•O(n log n) average, O(n^2) worst (bad pivot choices)
•Not stable: partitioning can change relative order of equal elements
•Random pivot or median-of-three helps avoid worst case

Gotchas

•Hoare partition returns j (not the pivot's final position) -- must recurse on [low..p] and [p+1..high], NOT [low..p-1]
•Lomuto on already-sorted input with last element as pivot gives O(n^2)
•Using Hoare partition with Lomuto-style recursive calls causes infinite recursion
•Stack overflow on O(n^2) worst case -- tail call optimization or iterative fallback needed

Pick pivot, partition so left < pivot < right, recurse on both halves. Lomuto: pivot at end, single scan. Hoare: two pointers from ends, fewer swaps. O(n log n) average, O(n^2) worst.

•O(n log n) average, not stable, in-place

int lomutoPartition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] <= pivot) { i++; int t=a[i]; a[i]=a[j]; a[j]=t; }
    int t=a[i+1]; a[i+1]=a[hi]; a[hi]=t;
    return i + 1;
}
void quicksort(int a[], int lo, int hi) {
    if (lo < hi) {
        int p = lomutoPartition(a, lo, hi);
        quicksort(a, lo, p-1);
        quicksort(a, p+1, hi);
    }
}

Already-sorted input with last-element pivot gives O(n^2)

Question 6 / 15

How do you implement binary search iteratively and recursively in C?

Binary search works on a sorted array. It repeatedly halves the search space by comparing the target with the middle element.

Algorithm:

Set low = 0, high = n - 1
While low <= high:
- Compute mid = low + (high - low) / 2
- If arr[mid] == target: found
- If arr[mid] < target: search right half (low = mid + 1)
- If arr[mid] > target: search left half (high = mid - 1)
If not found, return -1

Time: O(log n). Space: O(1) iterative, O(log n) recursive.

Critical: Use low + (high - low) / 2 instead of (low + high) / 2 to avoid integer overflow.

Pseudo Code

BinarySearch(arr, n, target):
  low = 0, high = n - 1
  while low <= high:
    mid = low + (high - low) / 2
    if arr[mid] == target: return mid
    if arr[mid] < target: low = mid + 1
    else: high = mid - 1
  return -1  // not found

BinarySearchRecursive(arr, low, high, target):
  if low > high: return -1
  mid = low + (high - low) / 2
  if arr[mid] == target: return mid
  if arr[mid] < target: return BSR(arr, mid+1, high, target)
  else: return BSR(arr, low, mid-1, target)

Code

#include <stdio.h>

/* Iterative binary search */
int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;  /* overflow-safe */

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;  /* not found */
}

/* Recursive binary search */
int binarySearchRecursive(int arr[], int low, int high, int target) {
    if (low > high)
        return -1;

    int mid = low + (high - low) / 2;

    if (arr[mid] == target)
        return mid;
    else if (arr[mid] < target)
        return binarySearchRecursive(arr, mid + 1, high, target);
    else
        return binarySearchRecursive(arr, low, mid - 1, target);
}

int main(void) {
    int arr[] = {2, 3, 4, 10, 40, 50, 70};
    int n = sizeof(arr) / sizeof(arr[0]);

    int idx = binarySearch(arr, n, 10);
    printf("Found 10 at index: %d\n", idx);  /* 3 */

    idx = binarySearch(arr, n, 5);
    printf("Found 5 at index: %d\n", idx);   /* -1 */

    idx = binarySearchRecursive(arr, 0, n - 1, 40);
    printf("Found 40 at index: %d\n", idx);  /* 4 */

    return 0;
}

Found 10 at index: 3
Found 5 at index: -1
Found 40 at index: 4

Key Points

•Array MUST be sorted for binary search to work
•O(log n) time -- halves search space each step
•Use low + (high - low) / 2 to avoid integer overflow
•Iterative preferred: O(1) space vs O(log n) for recursive
•Returns index of found element, -1 if not found

Gotchas

•(low + high) / 2 can overflow for large arrays -- always use low + (high - low) / 2
•Using binary search on an unsorted array gives wrong results
•Off-by-one: low <= high (not <) is the correct condition
•Using mid - 1 and mid + 1 (not just mid) is critical to avoid infinite loops

On a sorted array: compute mid, compare, search left or right half. O(log n). Use low + (high - low) / 2 to avoid overflow.

•O(log n), array must be sorted

int binarySearch(int arr[], int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

(low + high) / 2 overflows; use low + (high - low) / 2

Question 7 / 15

How do you implement linear search in C and when is it preferred over binary search?

Linear search scans elements one by one from start to end. It works on any array (sorted or unsorted).

Time: O(n) worst/average, O(1) best (found at first position). Space: O(1).

When to use linear search:

Array is unsorted (binary search requires sorted)
Array is very small (n < ~10, overhead of binary search not worth it)
Searching in a linked list (no random access)
Searching only once (sorting first would be O(n log n))

Sentinel optimization: Place the target at the end of the array, eliminating the bounds check in the loop. Reduces comparisons per iteration from 2 to 1.

Pseudo Code

LinearSearch(arr, n, target):
  for i = 0 to n-1:
    if arr[i] == target:
      return i
  return -1

SentinelSearch(arr, n, target):
  last = arr[n-1]
  arr[n-1] = target  // sentinel
  i = 0
  while arr[i] != target:
    i++
  arr[n-1] = last    // restore
  if i < n-1 or arr[n-1] == target:
    return i
  return -1

Code

#include <stdio.h>

/* Standard linear search */
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i;
    }
    return -1;
}

/* Sentinel linear search (eliminates bounds check) */
int sentinelSearch(int arr[], int n, int target) {
    int last = arr[n - 1];
    arr[n - 1] = target;  /* place sentinel */

    int i = 0;
    while (arr[i] != target)  /* no bounds check needed */
        i++;

    arr[n - 1] = last;  /* restore original value */

    if (i < n - 1 || arr[n - 1] == target)
        return i;
    return -1;
}

int main(void) {
    int arr[] = {2, 3, 4, 10, 40};
    int n = 5;

    printf("Found 10 at: %d\n", linearSearch(arr, n, 10));  /* 3 */
    printf("Found 5 at: %d\n", linearSearch(arr, n, 5));    /* -1 */

    printf("Sentinel 40 at: %d\n", sentinelSearch(arr, n, 40));  /* 4 */
    printf("Sentinel 99 at: %d\n", sentinelSearch(arr, n, 99));  /* -1 */

    return 0;
}

Found 10 at: 3
Found 5 at: -1
Sentinel 40 at: 4
Sentinel 99 at: -1

Key Points

•Works on sorted AND unsorted arrays
•O(n) time, O(1) space
•Sentinel optimization removes bounds check (one comparison per iteration instead of two)
•Preferred for small arrays, unsorted data, one-time searches
•Simplest searching algorithm

Gotchas

•Sentinel search modifies the array -- not safe for const arrays or concurrent access
•Linear search on large sorted arrays is wasteful -- use binary search
•For repeated searches, sorting once O(n log n) + binary search O(log n) beats repeated linear O(n)
•Sentinel search requires the array to have at least one element

Scan elements one by one. O(n) time, works on unsorted arrays. Use when array is small, unsorted, or searched only once.

•O(n), works on unsorted arrays

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++)
        if (arr[i] == target) return i;
    return -1;
}

Inefficient on large sorted arrays -- use binary search instead

Question 8 / 15

What is the time complexity analysis of common sorting algorithms?

Understanding time complexity is critical for choosing the right sorting algorithm.

Algorithm	Best	Average	Worst	Space	Stable?
Bubble Sort	O(n)	O(n^2)	O(n^2)	O(1)	Yes
Selection Sort	O(n^2)	O(n^2)	O(n^2)	O(1)	No
Insertion Sort	O(n)	O(n^2)	O(n^2)	O(1)	Yes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(n log n)	O(n^2)	O(log n)	No
Counting Sort	O(n+k)	O(n+k)	O(n+k)	O(n+k)	Yes
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No

Comparison-based lower bound: Any comparison-based sort must be at least O(n log n) in the worst case (proven via decision tree model).

Key insights:

O(n^2) sorts are good for small n or nearly sorted data (insertion sort)
Merge sort is the only O(n log n) stable sort with guaranteed performance
Quick sort is fastest in practice (good cache locality) but O(n^2) worst case
Counting sort breaks the O(n log n) barrier but requires integer keys in limited range

Pseudo Code

Comparison-based sorting lower bound: Omega(n log n)

Best for small n: Insertion sort (low overhead, adaptive)
Best guaranteed: Merge sort (always n log n, stable)
Best average: Quick sort (good cache, in-place)
Best for integers in range k: Counting sort (O(n+k))

Common interview answer for 'best sort':
  It depends on the data characteristics and constraints.

Code

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

/* Demonstrate complexity difference with timing */
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2)
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    free(L); free(R);
}

void mergeSort(int arr[], int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
}

int main(void) {
    int n = 10000;
    int *arr1 = (int *)malloc(n * sizeof(int));
    int *arr2 = (int *)malloc(n * sizeof(int));

    srand(42);
    for (int i = 0; i < n; i++)
        arr1[i] = arr2[i] = rand();

    clock_t start = clock();
    insertionSort(arr1, n);
    double t1 = (double)(clock() - start) / CLOCKS_PER_SEC;

    start = clock();
    mergeSort(arr2, 0, n - 1);
    double t2 = (double)(clock() - start) / CLOCKS_PER_SEC;

    printf("Insertion sort (n=%d): %.4f sec\n", n, t1);
    printf("Merge sort    (n=%d): %.4f sec\n", n, t2);
    /* Merge sort is dramatically faster for large n */

    free(arr1); free(arr2);
    return 0;
}

Insertion sort (n=10000): <time> sec
Merge sort    (n=10000): <time> sec
(Note: exact times vary; merge sort is significantly faster for large n)

Key Points

•Comparison-based sorts have Omega(n log n) lower bound
•Insertion sort: best for small/nearly-sorted data
•Merge sort: guaranteed O(n log n), stable, but O(n) space
•Quick sort: fastest in practice (cache-friendly), but O(n^2) worst
•Counting sort: O(n+k) breaks the n log n barrier for integer keys

Gotchas

•Quick sort's O(n^2) worst case can be triggered by sorted input with bad pivot
•O(n log n) is NOT always faster than O(n^2) for small n due to constant factors
•Merge sort's O(n) extra space is a real concern for embedded/memory-limited systems
•Stability matters when sorting objects by multiple keys

O(n^2): bubble, selection, insertion. O(n log n): merge (stable, O(n) space), quick (in-place, unstable, O(n^2) worst), heap. Comparison-based lower bound: O(n log n).

•O(n log n) is the lower bound for comparison-based sorts

/* Time complexity summary:
 * Bubble:    O(n^2) avg/worst, O(n) best  -- stable
 * Selection: O(n^2) always               -- unstable
 * Insertion: O(n^2) avg/worst, O(n) best  -- stable
 * Merge:     O(n log n) always            -- stable, O(n) space
 * Quick:     O(n log n) avg, O(n^2) worst -- unstable, O(log n) space
 * Counting:  O(n+k)                       -- stable, O(n+k) space
 */
int placeholder = 0;  /* valid C */

Quick sort's O(n^2) worst case is easily triggered on sorted input

Question 9 / 15

What is the space complexity comparison of common sorting algorithms?

Space complexity determines how much extra memory a sorting algorithm needs beyond the input array.

In-place sorts (O(1) extra space):

Bubble sort, selection sort, insertion sort, heap sort
Modify the array directly with only a few temporary variables

O(log n) extra space:

Quick sort: recursive call stack depth is O(log n) average, O(n) worst
Can be reduced to O(log n) worst with tail recursion optimization

O(n) extra space:

Merge sort: needs auxiliary array for merging
Counting sort: needs count array of size k (range of values)

Practical considerations:

Embedded systems with limited RAM prefer in-place sorts
Merge sort on linked lists is O(1) extra space (no auxiliary array needed)
Quick sort's stack space can be reduced by recursing on the smaller partition first

Pseudo Code

Space complexity:
  O(1):      Bubble, Selection, Insertion, Heap sort
  O(log n):  Quick sort (average stack depth)
  O(n):      Merge sort (auxiliary array), Quick sort (worst stack)
  O(n+k):   Counting sort (count array)

In-place means O(1) auxiliary space.
Recursive stack counts as space.

Code

#include <stdio.h>
#include <stdlib.h>

/* In-place sort: O(1) extra space */
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

/* O(n) space: merge sort needs auxiliary array */
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int *L = (int *)malloc(n1 * sizeof(int));  /* O(n) extra */
    int *R = (int *)malloc(n2 * sizeof(int));
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2)
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    free(L); free(R);
}

/* Quick sort with tail recursion optimization: O(log n) stack */
void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

int partition(int arr[], int lo, int hi) {
    int pivot = arr[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (arr[j] <= pivot) swap(&arr[++i], &arr[j]);
    swap(&arr[i + 1], &arr[hi]);
    return i + 1;
}

/* Tail-call optimized: always recurse on smaller half */
void quicksortOptimized(int arr[], int lo, int hi) {
    while (lo < hi) {
        int p = partition(arr, lo, hi);
        /* Recurse on smaller half, iterate on larger */
        if (p - lo < hi - p) {
            quicksortOptimized(arr, lo, p - 1);
            lo = p + 1;  /* tail call elimination */
        } else {
            quicksortOptimized(arr, p + 1, hi);
            hi = p - 1;  /* tail call elimination */
        }
    }
}

int main(void) {
    int arr[] = {5, 2, 8, 1, 9, 3};
    int n = 6;

    insertionSort(arr, n);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");  /* 1 2 3 5 8 9 */

    return 0;
}

1 2 3 5 8 9

Key Points

•In-place (O(1)): bubble, selection, insertion, heap sort
•Quick sort: O(log n) average stack, O(n) worst -- optimizable with tail recursion
•Merge sort: O(n) auxiliary array -- cannot be avoided for arrays
•Recursive stack space counts toward space complexity
•Merge sort on linked lists uses O(1) extra space (O(log n) stack)

Gotchas

•Quick sort's O(log n) is AVERAGE -- worst case is O(n) stack depth
•In-place does NOT mean O(0) -- it means O(1) auxiliary space
•Merge sort's O(n) space is per merge call but reusable -- total extra is O(n)
•Tail-call optimization for quick sort is not automatic in C -- must be done manually

In-place O(1): bubble, selection, insertion, heap. Quick sort: O(log n) avg stack. Merge sort: O(n) auxiliary. Counting sort: O(n+k). Recursive stack counts as space.

•In-place = O(1) extra, not O(0)

/* Space complexity:
 * O(1):     bubble, selection, insertion, heap (in-place)
 * O(log n): quick sort (average call stack)
 * O(n):    merge sort (auxiliary array), quick (worst stack)
 * O(n+k):  counting sort
 *
 * Tail-call optimization for quicksort:
 *   Always recurse on smaller partition, loop on larger.
 */
int placeholder = 0;

Quick sort worst-case stack depth is O(n), not O(log n)

Question 10 / 15

Which sorting algorithms are stable and why does stability matter?

A stable sort preserves the relative order of elements with equal keys. If two elements have the same sort key, they appear in the same order in the output as they did in the input.

Stable sorts: Bubble sort, insertion sort, merge sort, counting sort, Timsort.

Unstable sorts: Selection sort, quick sort, heap sort.

Why stability matters:

Multi-key sorting: Sort by last name, then by first name. If the second sort is stable, people with the same first name stay in last-name order.
Preserving prior work: When re-sorting already partially sorted data.
Correctness requirements: Some algorithms and data structures depend on stable sorting.

Making unstable sorts stable:

Add the original index as a secondary key (extra O(n) space)
Quick sort can be made stable with extra space (but defeats its in-place advantage)

Pseudo Code

Stability definition:
  If a[i] == a[j] and i < j in input,
  then a[i] appears before a[j] in output.

Stable:   Bubble, Insertion, Merge, Counting, Timsort
Unstable: Selection, Quick, Heap

Example: Sorting students by grade (stable):
  Input:  [(Alice, B), (Bob, A), (Carol, B), (Dave, A)]
  Stable: [(Bob, A), (Dave, A), (Alice, B), (Carol, B)]
  Unstable might give: [(Dave, A), (Bob, A), (Carol, B), (Alice, B)]

Code

#include <stdio.h>
#include <string.h>

typedef struct {
    char name[20];
    int grade;
} Student;

/* Stable insertion sort (preserves order of equal grades) */
void stableSort(Student arr[], int n) {
    for (int i = 1; i < n; i++) {
        Student key = arr[i];
        int j = i - 1;
        /* > (not >=) ensures stability */
        while (j >= 0 && arr[j].grade > key.grade) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

/* Unstable selection sort (may change relative order) */
void unstableSort(Student arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j].grade < arr[min].grade)
                min = j;
        if (min != i) {
            Student temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

int main(void) {
    Student s1[] = {
        {"Alice", 2}, {"Bob", 1}, {"Carol", 2}, {"Dave", 1}
    };
    Student s2[] = {
        {"Alice", 2}, {"Bob", 1}, {"Carol", 2}, {"Dave", 1}
    };

    stableSort(s1, 4);
    printf("Stable sort:\n");
    for (int i = 0; i < 4; i++)
        printf("  %s (grade %d)\n", s1[i].name, s1[i].grade);
    /* Bob(1), Dave(1), Alice(2), Carol(2) -- original order preserved */

    unstableSort(s2, 4);
    printf("Unstable sort:\n");
    for (int i = 0; i < 4; i++)
        printf("  %s (grade %d)\n", s2[i].name, s2[i].grade);
    /* May give Dave(1), Bob(1) -- relative order not guaranteed */

    return 0;
}

Stable sort:
  Bob (grade 1)
  Dave (grade 1)
  Alice (grade 2)
  Carol (grade 2)
Unstable sort:
  Bob (grade 1)
  Dave (grade 1)
  Carol (grade 2)
  Alice (grade 2)

Key Points

•Stable sort preserves relative order of equal elements
•Stable: bubble, insertion, merge, counting. Unstable: selection, quick, heap
•Using > (not >=) in comparison makes insertion sort stable
•Matters for multi-key sorting and preserving prior orderings
•Can make any sort stable by adding original index as tiebreaker

Gotchas

•Using >= instead of > in insertion sort's comparison breaks stability
•Quick sort is unstable due to partitioning swaps -- cannot be made stable without extra space
•Selection sort is unstable because the swap can jump over equal elements
•qsort() from stdlib does NOT guarantee stability

Stable sort preserves order of equal elements. Stable: bubble, insertion, merge, counting. Unstable: selection, quick, heap. Matters for multi-key sorting.

•Stable: bubble, insertion, merge. Unstable: selection, quick, heap

/* Stability: using > (not >=) preserves order of equal keys */
void stableInsertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) {  /* > not >= for stability */
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

Using >= instead of > breaks stability in insertion sort

Question 11 / 15

How do you use qsort() from stdlib.h and write comparator functions?

C's qsort() from <stdlib.h> is a generic sorting function that works with any data type via a comparator function.

Signature:

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

Comparator contract:

Return negative if a < b
Return 0 if a == b
Return positive if a > b

Common patterns:

Integers: return *(int*)a - *(int*)b;
Strings: return strcmp(*(char**)a, *(char**)b);
Structs: Cast to struct pointer, compare the desired field
Reverse order: swap a and b, or negate the result

Note: qsort is NOT guaranteed to be stable. The implementation varies (typically quicksort or introsort).

Pseudo Code

qsort(array, count, element_size, comparator)

Comparator signature:
  int compare(const void *a, const void *b)
  return < 0 if a < b
  return 0   if a == b
  return > 0 if a > b

For integers: *(int*)a - *(int*)b
For strings: strcmp(*(char**)a, *(char**)b)
For descending: swap a and b in the comparison

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Compare integers (ascending) */
int compareInt(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

/* Compare integers (descending) */
int compareIntDesc(const void *a, const void *b) {
    return (*(int *)b - *(int *)a);
}

/* Compare strings */
int compareStr(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

/* Compare structs by field */
typedef struct {
    char name[50];
    int score;
} Player;

int compareByScore(const void *a, const void *b) {
    const Player *pa = (const Player *)a;
    const Player *pb = (const Player *)b;
    return pa->score - pb->score;
}

/* Overflow-safe integer comparison */
int compareIntSafe(const void *a, const void *b) {
    int ia = *(const int *)a;
    int ib = *(const int *)b;
    if (ia < ib) return -1;
    if (ia > ib) return 1;
    return 0;
}

int main(void) {
    /* Sort integers */
    int nums[] = {40, 10, 100, 90, 20};
    int n = 5;
    qsort(nums, n, sizeof(int), compareInt);
    for (int i = 0; i < n; i++) printf("%d ", nums[i]);
    printf("\n");  /* 10 20 40 90 100 */

    /* Sort strings */
    const char *words[] = {"banana", "apple", "cherry"};
    qsort(words, 3, sizeof(char *), compareStr);
    for (int i = 0; i < 3; i++) printf("%s ", words[i]);
    printf("\n");  /* apple banana cherry */

    /* Sort structs */
    Player players[] = {{"Alice", 90}, {"Bob", 75}, {"Carol", 88}};
    qsort(players, 3, sizeof(Player), compareByScore);
    for (int i = 0; i < 3; i++)
        printf("%s(%d) ", players[i].name, players[i].score);
    printf("\n");  /* Bob(75) Carol(88) Alice(90) */

    return 0;
}

10 20 40 90 100 
apple banana cherry 
Bob(75) Carol(88) Alice(90)

Key Points

•qsort() works with any type via void pointers and a comparator function
•Comparator returns negative (a<b), zero (a==b), positive (a>b)
•Must cast void pointers to the correct type inside comparator
•For strings (char**), dereference twice: *(const char**)a
•qsort is NOT guaranteed to be stable

Gotchas

•a - b for integers can OVERFLOW (e.g., INT_MIN - 1) -- use if/else comparison for safety
•For array of strings (char*[]), comparator receives char**, not char* -- must dereference
•Passing wrong element size to qsort silently corrupts memory
•qsort modifies the array in-place -- cannot sort const arrays

qsort(arr, n, sizeof(elem), comparator). Comparator takes two const void*, returns negative/zero/positive. Cast void pointers to correct type inside comparator.

•Generic sorting via void* and comparator function

int cmpInt(const void *a, const void *b) {
    return *(int*)a - *(int*)b;  /* ascending */
}
int cmpStr(const void *a, const void *b) {
    return strcmp(*(const char**)a, *(const char**)b);
}

int arr[] = {5, 2, 8, 1};
qsort(arr, 4, sizeof(int), cmpInt);  /* 1 2 5 8 */

a - b overflows for large ints -- use if/else for safety

Question 12 / 15

How do you use bsearch() from stdlib.h for binary search?

C's bsearch() from <stdlib.h> performs binary search on a sorted array using the same comparator concept as qsort().

Signature:

void *bsearch(const void *key, const void *base, size_t nmemb,
              size_t size, int (*compar)(const void *, const void *));

Parameters:

key: pointer to the value to search for
base: pointer to the sorted array
nmemb: number of elements
size: size of each element
compar: comparator function (same as qsort)

Return: Pointer to the found element, or NULL if not found.

Important: The array MUST be sorted in the same order as the comparator expects. If duplicates exist, bsearch may return ANY of them (not necessarily the first).

Pseudo Code

bsearch(key_ptr, array, count, elem_size, comparator)

Returns:
  Pointer to matching element, or NULL

Requirements:
  Array must be sorted (ascending by comparator)
  Same comparator used for qsort and bsearch

Usage pattern:
  qsort(arr, n, sizeof(T), cmp);  // sort first
  T *found = bsearch(&key, arr, n, sizeof(T), cmp);

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmpInt(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b;
}

int cmpStr(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

typedef struct {
    int id;
    char name[50];
} Record;

int cmpRecord(const void *a, const void *b) {
    return ((const Record *)a)->id - ((const Record *)b)->id;
}

int main(void) {
    /* Search in sorted integer array */
    int nums[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = 10;
    int key = 23;
    int *found = (int *)bsearch(&key, nums, n, sizeof(int), cmpInt);
    if (found)
        printf("Found %d at index %ld\n", *found, found - nums);  /* index 5 */
    else
        printf("Not found\n");

    /* Search for non-existent value */
    key = 25;
    found = (int *)bsearch(&key, nums, n, sizeof(int), cmpInt);
    printf("25: %s\n", found ? "found" : "not found");  /* not found */

    /* Search in sorted string array */
    const char *words[] = {"apple", "banana", "cherry", "date", "fig"};
    const char *target = "cherry";
    const char **result = (const char **)bsearch(&target, words, 5,
                                                  sizeof(char *), cmpStr);
    if (result)
        printf("Found: %s\n", *result);  /* cherry */

    /* Search in struct array */
    Record records[] = {{1, "Alice"}, {5, "Bob"}, {10, "Carol"}, {15, "Dave"}};
    Record searchKey = {10, ""};
    Record *rec = (Record *)bsearch(&searchKey, records, 4,
                                     sizeof(Record), cmpRecord);
    if (rec)
        printf("Found: id=%d name=%s\n", rec->id, rec->name);  /* Carol */

    return 0;
}

Found 23 at index 5
25: not found
Found: cherry
Found: id=10 name=Carol

Key Points

•bsearch() returns a pointer to the found element or NULL
•Array MUST be sorted (same order as comparator)
•Same comparator pattern as qsort()
•First argument is pointer to the key (not the key value itself)
•Returns void* -- must cast to the correct type

Gotchas

•Array must be sorted BEFORE calling bsearch -- calling on unsorted gives undefined results
•For duplicates, bsearch may return ANY matching element (not necessarily the first)
•key is a pointer: pass &key, not key directly
•Using a different comparator for qsort and bsearch is undefined behavior

bsearch(&key, arr, n, sizeof(elem), cmp) searches a sorted array. Returns pointer to found element or NULL. Same comparator as qsort.

•Returns pointer to match or NULL, array must be sorted

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int arr[] = {1, 3, 5, 7, 9};
int key = 5;
int *found = (int *)bsearch(&key, arr, 5, sizeof(int), cmp);
if (found) printf("Found at index %ld\n", found - arr);  /* 2 */

Pass &key (pointer to key), not the key value itself

Question 13 / 15

How do you implement counting sort in C?

Counting sort is a non-comparison-based sorting algorithm that works by counting the frequency of each distinct value.

Algorithm:

Find the range of values (min to max)
Create a count array of size (max - min + 1)
Count occurrences of each value
Compute prefix sums (cumulative count)
Build the output array using the counts

Time: O(n + k) where k is the range of values. Space: O(n + k). Stable: Yes (when implemented with prefix sums and backward iteration).

Best for: Integer keys in a known, limited range. Beats comparison sorts when k = O(n).

Not suitable for: Floating-point data, very large ranges, or when values are spread over a huge range.

Pseudo Code

CountingSort(arr, n):
  Find min and max of arr
  k = max - min + 1
  Create count[k] initialized to 0
  For each element: count[arr[i] - min]++
  Prefix sum: count[i] += count[i-1]
  Build output (iterate backwards for stability):
    output[count[arr[i]-min] - 1] = arr[i]
    count[arr[i]-min]--
  Copy output back to arr

Code

#include <stdio.h>
#include <stdlib.h>

/* Counting sort for non-negative integers */
void countingSort(int arr[], int n) {
    if (n <= 1) return;

    /* Find range */
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }

    int range = max - min + 1;
    int *count = (int *)calloc(range, sizeof(int));
    int *output = (int *)malloc(n * sizeof(int));

    /* Count occurrences */
    for (int i = 0; i < n; i++)
        count[arr[i] - min]++;

    /* Prefix sum */
    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];

    /* Build output (iterate backwards for stability) */
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    /* Copy back */
    for (int i = 0; i < n; i++)
        arr[i] = output[i];

    free(count);
    free(output);
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main(void) {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Before: ");
    printArray(arr, n);

    countingSort(arr, n);

    printf("After:  ");
    printArray(arr, n);  /* 1 2 2 3 3 4 8 */

    /* Works with negative numbers too */
    int arr2[] = {-5, -2, 3, 0, -1, 2};
    int n2 = 6;
    countingSort(arr2, n2);
    printf("Neg:    ");
    printArray(arr2, n2);  /* -5 -2 -1 0 2 3 */

    return 0;
}

Before: 4 2 2 8 3 3 1 
After:  1 2 2 3 3 4 8 
Neg:    -5 -2 -1 0 2 3

Key Points

•O(n + k) time where k = range of values
•Not comparison-based -- breaks the O(n log n) lower bound
•Stable when iterating backwards to build output
•Best for integer keys in a limited range
•Prefix sum step transforms counts into positions

Gotchas

•Huge range (e.g., 0 to 10^9) makes count array impractical -- O(k) space
•Forward iteration in the output step breaks stability
•Forgetting to handle negative numbers (use min offset)
•calloc vs malloc: count array MUST be initialized to 0

Count frequency of each value, prefix sum to get positions, build output backward (for stability). O(n+k) time/space. Only for integers in limited range.

•O(n+k), stable, non-comparison-based

void countingSort(int arr[], int n) {
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
    int range = max - min + 1;
    int *count = (int *)calloc(range, sizeof(int));
    int *output = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) count[arr[i]-min]++;
    for (int i = 1; i < range; i++) count[i] += count[i-1];
    for (int i = n-1; i >= 0; i--)
        output[--count[arr[i]-min]] = arr[i];
    for (int i = 0; i < n; i++) arr[i] = output[i];
    free(count); free(output);
}

Impractical when range k >> n

Question 14 / 15

When should you use which sorting algorithm in practice?

Choosing the right sorting algorithm depends on data characteristics and constraints.

Use Insertion Sort when:

Array is small (n < 50)
Data is nearly sorted (O(n) in this case)
Online sorting (elements arrive one at a time)
Used as base case inside quicksort/mergesort

Use Merge Sort when:

Stability is required
Guaranteed O(n log n) is needed (no worst-case degradation)
Sorting linked lists (no random access needed, O(1) extra space)
External sorting (data too large for RAM)

Use Quick Sort when:

Average-case performance matters most
In-place sorting is needed
Cache performance is important
Used in most standard libraries (C's qsort, etc.)

Use Counting/Radix Sort when:

Keys are integers in a known, limited range
O(n) time is needed

Use Heap Sort when:

Guaranteed O(n log n) AND in-place (O(1) space) are both needed
Worst-case guarantee without extra memory

In practice: Most standard libraries use hybrid algorithms (Timsort = merge + insertion, Introsort = quick + heap + insertion).

Pseudo Code

Decision tree:
  Is n small (< 50)?          -> Insertion sort
  Is data nearly sorted?       -> Insertion sort
  Need stability?              -> Merge sort
  Need guaranteed O(n log n)?  -> Merge sort or Heap sort
  Need O(1) space + O(n log n)? -> Heap sort
  Integer keys, small range?   -> Counting sort
  General purpose?             -> Quick sort (or introsort)
  Sorting linked list?         -> Merge sort
  External sorting (disk)?     -> Merge sort

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Hybrid approach: use insertion sort for small subarrays */
#define INSERTION_THRESHOLD 16

void insertionSort(int arr[], int lo, int hi) {
    for (int i = lo + 1; i <= hi; i++) {
        int key = arr[i], j = i - 1;
        while (j >= lo && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

int partition(int arr[], int lo, int hi) {
    /* Median-of-three pivot */
    int mid = lo + (hi - lo) / 2;
    if (arr[lo] > arr[mid]) swap(&arr[lo], &arr[mid]);
    if (arr[lo] > arr[hi]) swap(&arr[lo], &arr[hi]);
    if (arr[mid] > arr[hi]) swap(&arr[mid], &arr[hi]);
    swap(&arr[mid], &arr[hi - 1]);  /* pivot at hi-1 */
    int pivot = arr[hi - 1];
    int i = lo, j = hi - 1;
    while (1) {
        while (arr[++i] < pivot);
        while (arr[--j] > pivot);
        if (i >= j) break;
        swap(&arr[i], &arr[j]);
    }
    swap(&arr[i], &arr[hi - 1]);
    return i;
}

/* Hybrid quicksort: switches to insertion sort for small partitions */
void hybridSort(int arr[], int lo, int hi) {
    if (hi - lo < INSERTION_THRESHOLD) {
        insertionSort(arr, lo, hi);
        return;
    }
    int p = partition(arr, lo, hi);
    hybridSort(arr, lo, p - 1);
    hybridSort(arr, p + 1, hi);
}

int main(void) {
    int arr[] = {38, 27, 43, 3, 9, 82, 10, 15, 44, 2, 7, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    hybridSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");  /* 1 2 3 7 9 10 15 27 38 43 44 82 */

    return 0;
}

1 2 3 7 9 10 15 27 38 43 44 82

Key Points

•No single best sorting algorithm -- depends on constraints
•Insertion sort for small arrays and nearly sorted data
•Merge sort for stability and guaranteed O(n log n)
•Quick sort for best average-case performance
•Real-world libraries use hybrid approaches (introsort, timsort)

Gotchas

•Quick sort degrades to O(n^2) on already-sorted input without good pivot selection
•Merge sort's O(n) extra space is prohibitive for embedded systems
•Counting sort is useless when key range >> n
•Heap sort has poor cache locality despite O(n log n) guarantee

Small/nearly-sorted: insertion sort. Need stability: merge sort. General purpose: quicksort. Integer keys, small range: counting sort. In-place + guaranteed: heap sort. Real libraries use hybrids.

•Choice depends on data size, distribution, stability needs, and memory constraints

/* Algorithm selection guide:
 * Small n (<50):         Insertion sort
 * Nearly sorted:         Insertion sort  O(n)
 * Need stability:        Merge sort      O(n log n)
 * General purpose:       Quick sort      O(n log n) avg
 * In-place + guarantee:  Heap sort       O(n log n)
 * Integer, small range:  Counting sort   O(n+k)
 * Linked list:           Merge sort      O(1) space
 * Hybrid (production):   Introsort or Timsort
 */
int placeholder = 0;

No single algorithm is best for all cases -- interviewers expect nuanced answers

Question 15 / 15

How do you solve common interview problems like finding the kth largest element and searching in a rotated sorted array?

Finding kth largest element:

Sort approach: Sort descending, return arr[k-1]. O(n log n)
Quickselect (optimal): Partition-based selection. Average O(n), worst O(n^2). Uses the same partition as quicksort but only recurses on the relevant side.

Search in rotated sorted array: A sorted array rotated at some pivot (e.g., [4,5,6,7,0,1,2]). Binary search with modification:

At each step, one half is always sorted
Check if the target is in the sorted half
If yes, search that half; otherwise search the other half

Both are extremely common interview questions that combine sorting/searching concepts.

Pseudo Code

Quickselect(arr, left, right, k):
  if left == right: return arr[left]
  pivotIndex = partition(arr, left, right)
  if k == pivotIndex: return arr[k]
  if k < pivotIndex: return Quickselect(arr, left, pivotIndex-1, k)
  else: return Quickselect(arr, pivotIndex+1, right, k)

SearchRotated(arr, n, target):
  lo = 0, hi = n-1
  while lo <= hi:
    mid = lo + (hi-lo)/2
    if arr[mid] == target: return mid
    if arr[lo] <= arr[mid]:  // left half sorted
      if arr[lo] <= target < arr[mid]: hi = mid-1
      else: lo = mid+1
    else:  // right half sorted
      if arr[mid] < target <= arr[hi]: lo = mid+1
      else: hi = mid-1

Code

#include <stdio.h>

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

int partition(int arr[], int lo, int hi) {
    int pivot = arr[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (arr[j] <= pivot)
            swap(&arr[++i], &arr[j]);
    swap(&arr[i + 1], &arr[hi]);
    return i + 1;
}

/* Find kth smallest element (0-indexed) using Quickselect: avg O(n) */
int quickselect(int arr[], int lo, int hi, int k) {
    if (lo == hi) return arr[lo];

    int pivotIdx = partition(arr, lo, hi);

    if (k == pivotIdx)
        return arr[k];
    else if (k < pivotIdx)
        return quickselect(arr, lo, pivotIdx - 1, k);
    else
        return quickselect(arr, pivotIdx + 1, hi, k);
}

/* Find kth largest: kth largest = (n-k)th smallest */
int findKthLargest(int arr[], int n, int k) {
    return quickselect(arr, 0, n - 1, n - k);
}

/* Search in rotated sorted array: O(log n) */
int searchRotated(int arr[], int n, int target) {
    int lo = 0, hi = n - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == target)
            return mid;

        /* Left half is sorted */
        if (arr[lo] <= arr[mid]) {
            if (target >= arr[lo] && target < arr[mid])
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        /* Right half is sorted */
        else {
            if (target > arr[mid] && target <= arr[hi])
                lo = mid + 1;
            else
                hi = mid - 1;
        }
    }
    return -1;
}

int main(void) {
    /* Kth largest */
    int arr1[] = {3, 2, 1, 5, 6, 4};
    printf("2nd largest: %d\n", findKthLargest(arr1, 6, 2));  /* 5 */

    int arr2[] = {3, 2, 3, 1, 2, 4, 5, 5, 6};
    printf("4th largest: %d\n", findKthLargest(arr2, 9, 4));  /* 4 */

    /* Rotated array search */
    int rotated[] = {4, 5, 6, 7, 0, 1, 2};
    int n = 7;
    printf("Search 0: index %d\n", searchRotated(rotated, n, 0));  /* 4 */
    printf("Search 3: index %d\n", searchRotated(rotated, n, 3));  /* -1 */
    printf("Search 6: index %d\n", searchRotated(rotated, n, 6));  /* 2 */

    return 0;
}

2nd largest: 5
4th largest: 4
Search 0: index 4
Search 3: index -1
Search 6: index 2

Key Points

•Quickselect: average O(n), uses partition but only recurses on one side
•kth largest = (n-k)th smallest
•Rotated array: one half is always sorted -- binary search with extra condition
•Both are top-10 most asked interview questions
•Quickselect modifies the array (partial sorting)

Gotchas

•Quickselect worst case is O(n^2) -- random pivot helps
•Quickselect modifies the input array -- make a copy if original order matters
•Rotated array with duplicates requires O(n) worst case -- the O(log n) approach fails
•Off-by-one in kth largest: 1st largest is the max, not the 0th

Kth largest: Quickselect with k = n-k for 0-indexed. Average O(n). Rotated array: Modified binary search -- one half is always sorted, check if target is in that range. O(log n).

•Quickselect O(n) avg, rotated search O(log n)

int searchRotated(int arr[], int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi-lo)/2;
        if (arr[mid] == target) return mid;
        if (arr[lo] <= arr[mid]) {
            if (target >= arr[lo] && target < arr[mid]) hi = mid-1;
            else lo = mid+1;
        } else {
            if (target > arr[mid] && target <= arr[hi]) lo = mid+1;
            else hi = mid-1;
        }
    }
    return -1;
}

Rotated array with duplicates degrades to O(n)

Built by onllm.dev

Home GitHub Support awesomePrep