C Algorithms: Big-O Complexity, Searching & 5 Sorting Algorithms Masterclass
Welcome to Phase 19 (Chapter 52): C Algorithms ā Big-O Complexity, Searching & 5 Sorting Algorithms Masterclass! Algorithm efficiency determines whether software handles millions of requests or freezes instantly. In this guide, you will master asymptotic notation (Big-O), search algorithms, and 5 foundational sorting algorithms with complete C source code and dry runs.
Big-O notation describes the upper bound of execution time or memory growth relative to input size N as N grows toward infinity.
| Big-O Class | Name | Example Operations | Growth for N = 1,000,000 |
|---|---|---|---|
O(1) | Constant Time | Array index lookup, Stack push/pop | 1 operation |
O(log N) | Logarithmic Time | Binary search in sorted array | ~20 operations |
O(N) | Linear Time | Linear search, finding max value | 1,000,000 operations |
O(N log N) | Linearithmic Time | Merge Sort, Quick Sort (average) | ~20,000,000 operations |
O(NĀ²) | Quadratic Time | Bubble Sort, Selection Sort | 1,000,000,000,000 operations (Slow!) |
Linear Search checks elements sequentially in O(N) time. Binary Search requires a sorted array and repeatedly divides the search range in half in O(log N) time.
#include <stdio.h>
#include <stdlib.h>
/* QUICK SORT - O(N log N) Average */
static void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }
static int partition(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 quick_sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}
int main(void) {
int numbers[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(numbers) / sizeof(numbers[0]);
printf("Unsorted: ");
for (int i = 0; i < n; i++) printf("%d ", numbers[i]);
printf("\n");
quick_sort(numbers, 0, n - 1);
printf("Quick Sorted: ");
for (int i = 0; i < n; i++) printf("%d ", numbers[i]);
printf("\n");
return 0;
}| Algorithm | Best Time | Average Time | Worst Time | Space | Stable? |
|---|---|---|---|---|---|
| Bubble Sort | O(N) | O(NĀ²) | O(NĀ²) | O(1) | Yes |
| Selection Sort | O(NĀ²) | O(NĀ²) | O(NĀ²) | O(1) | No |
| Insertion Sort | O(N) | O(NĀ²) | O(NĀ²) | 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Ā²) | O(log N) | No |
Q1: What does sorting stability mean?
A sorting algorithm is stable if equal keys retain their relative original order after sorting. Important when sorting records by multiple criteria.
Q2: Why is Quick Sort preferred over Merge Sort in practice?
Quick Sort sorts in-place with lower cache-miss constants, whereas Merge Sort requires extra O(N) heap memory allocation for merging sub-arrays.
Q3: How do you prevent Quick Sort worst-case O(NĀ²)?
Use randomized pivot selection or median-of-three pivot selection to prevent bad partitions on already-sorted arrays.
Q4: When is Insertion Sort better than Quick Sort?
Insertion Sort is extremely fast for small arrays (N < 15) or nearly sorted arrays due to minimal overhead and O(N) best-case complexity.
Q5: What is the theoretical lower bound for comparison sorting?
Any comparison-based sorting algorithm requires at least Ī©(N log N) comparisons in the worst case.