Algorithm Complexity
Understanding algorithm complexity is like learning to read a map before taking a road trip. It helps you predict how your code will perform as data grows, letting you choose the right algorithm before performance becomes a problem. Algorithm complexity measures how execution time and memory usage scale with input size, giving you a scientific way to compare different approaches. Mastering this concept transforms you from someone who writes code that works to someone who writes code that works efficiently at any scale.
Big O Notation
Big O notation describes how an algorithm's runtime or space requirements grow as the input
size increases. Written as O(f(n)), where n is the input size and f(n)
represents the growth rate. It focuses on the worst-case scenario and ignores constant factors and lower-order
terms, giving you a high-level view of scalability.
Think of Big O as answering "How bad can it get?" If you double your data, does execution time double?
Quadruple? Stay the same? Big O tells you this growth pattern. An O(1) algorithm takes constant
time regardless of input size. O(n) scales linearly with input. O(n²) scales with
the square of input, becoming dramatically slower as data grows.
Key insight: Big O ignores constants and focuses on growth rate. An algorithm that takes
5n + 10 operations is still O(n) because linear growth dominates as n gets large.
O(1): Constant Time
#include <iostream>
using namespace std;
int getFirstElement(int arr[], int size) {
return arr[0]; // Always one operation
}
int main() {
int numbers[] = {42, 15, 8, 23, 16};
int result = getFirstElement(numbers, 5);
cout << result << endl; // Result: 42
// Works same speed regardless of array size!
int huge[1000000];
huge[0] = 99;
result = getFirstElement(huge, 1000000);
cout << result << endl; // Result: 99 (same speed!)
return 0;
}This demonstrates O(1) constant time complexity. Array access by index takes the same amount of time whether the array has 5 elements or 5 million. The CPU can jump directly to any memory location, making this operation independent of data size. Other O(1) operations include arithmetic, variable assignment, and accessing structure members.
O(n): Linear Time
#include <iostream>
using namespace std;
int findMax(int arr[], int size) {
int maxValue = arr[0];
for (int i = 1; i < size; i++) {
if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
return maxValue;
}
int main() {
int numbers[] = {42, 15, 89, 23, 16};
int maximum = findMax(numbers, 5);
cout << "Max: " << maximum << endl; // Result: Max: 89
return 0;
}This shows O(n) linear time complexity. To find the maximum value, we must examine every element exactly once. If you double the array size, execution time doubles. If you have 1,000 elements, you do roughly 1,000 comparisons. This linear relationship between input size and operations is characteristic of algorithms that must process each element at least once.
O(n²): Quadratic Time
#include <iostream>
using namespace std;
void printAllPairs(int arr[], int size) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
cout << "(" << arr[i] << ", "
<< arr[j] << ") ";
}
}
}
int main() {
int numbers[] = {1, 2, 3};
printAllPairs(numbers, 3);
// Result: (1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)
return 0;
}This illustrates O(n²) quadratic time complexity. Nested loops create quadratic behavior because for each of n elements in the outer loop, you process n elements in the inner loop, giving n × n = n² operations. With 3 elements, you get 9 pairs. With 100 elements, you get 10,000 pairs. This growth becomes problematic quickly, which is why algorithms like bubble sort (O(n²)) struggle with large datasets while merge sort (O(n log n)) excels.
Common Complexity Classes
Here's how different complexity classes compare when processing 1,000 elements. Notice how exponential complexities become completely impractical while logarithmic and linear complexities remain manageable even at large scales.
| Complexity | Name | Operations for n=1000 | Common Examples |
|---|---|---|---|
O(1) |
Constant | 1 | Array access, hash table lookup, stack push/pop |
O(log n) |
Logarithmic | ~10 | Binary search, balanced tree operations |
O(n) |
Linear | 1,000 | Linear search, array traversal, finding min/max |
O(n log n) |
Linearithmic | ~10,000 | Merge sort, quick sort (average), heap sort |
O(n²) |
Quadratic | 1,000,000 | Bubble sort, insertion sort, nested loops |
O(2ⁿ) |
Exponential | ~10³⁰⁰ (impractical!) | Recursive fibonacci (naive), subset generation |
Space Complexity Analysis
While time complexity measures how execution time grows, space complexity measures how memory usage grows with input size. Every algorithm needs memory for variables, and some need additional space for temporary storage like auxiliary arrays or recursion call stacks. Space complexity becomes critical when working with large datasets or memory-constrained environments like embedded systems, mobile devices, or when processing data that barely fits in RAM.
Understanding space complexity helps you make informed trade-offs. Sometimes you can reduce time complexity by using more memory (like caching results), or save memory by accepting slower execution. The key is knowing the cost of each approach so you can choose wisely based on your constraints.
O(1): Constant Space
#include <iostream>
using namespace std;
void reverseArray(int arr[], int size) {
int left = 0, right = size - 1;
while (left < right) {
// Swap using only 1 temporary variable
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
int main() {
int numbers[] = {1, 2, 3, 4, 5};
reverseArray(numbers, 5);
// Result: {5, 4, 3, 2, 1}
return 0;
}This demonstrates O(1) constant space complexity. The function uses only a fixed number of variables (left, right, temp) regardless of array size. Whether you reverse 5 elements or 5 million, memory usage stays constant. This is called an in-place algorithm because it modifies the input without requiring additional space proportional to input size. In-place algorithms are valuable when memory is limited or when you're working with massive datasets.
O(n): Linear Space
#include <iostream>
using namespace std;
int* createCopy(int arr[], int size) {
// Allocate new array with same size
int* copy = new int[size];
for (int i = 0; i < size; i++) {
copy[i] = arr[i];
}
return copy;
}
int main() {
int original[] = {10, 20, 30, 40, 50};
int* duplicate = createCopy(original, 5);
// Result: duplicate is {10, 20, 30, 40, 50}
delete[] duplicate; // Don't forget to free memory!
return 0;
}This shows O(n) linear space complexity. The function allocates a new array of size n, so memory usage grows linearly with input size. If you double the input size, you double the memory needed. Many algorithms require O(n) auxiliary space, like merge sort which needs temporary arrays for merging. While this uses more memory than in-place algorithms, it often enables faster execution or preserves the original data.
Space-Time Trade-off: Fibonacci
#include <iostream>
using namespace std;
// O(2ⁿ) time, O(n) space (recursion stack)
int fibRecursive(int n) {
if (n <= 1) return n;
return fibRecursive(n-1) + fibRecursive(n-2);
}
// O(n) time, O(n) space (array storage)
int fibMemoization(int n, int memo[]) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fibMemoization(n-1, memo) + fibMemoization(n-2, memo);
return memo[n];
}
// O(n) time, O(1) space (only 2 variables!)
int fibIterative(int n) {
if (n <= 1) return n;
int prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
int next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}These three Fibonacci implementations demonstrate the space-time trade-off. The naive recursive version is slow (exponential time) and uses O(n) space for the recursion call stack. Memoization trades O(n) extra space for dramatically faster O(n) time by caching results. The iterative version achieves the best of both worlds: O(n) time with only O(1) space by tracking just two previous values. This shows how clever algorithm design can optimize both time and space simultaneously.
Practice Questions
Given:
int numbers[] = {10, 25, 30, 45, 50};
int target = 30;Task: Write a C++ function contains() that searches an array for a target value and returns true if found, false otherwise. What is the time complexity?
View Solution
#include <iostream>
using namespace std;
bool contains(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return true;
}
}
return false;
}
int main() {
int numbers[] = {10, 25, 30, 45, 50};
cout << contains(numbers, 5, 30) << endl; // Result: 1 (true)
cout << contains(numbers, 5, 99) << endl; // Result: 0 (false)
return 0;
}
// Time Complexity: O(n) - must check up to n elementsGiven:
int numbers[] = {5, 2, 8, 2, 9, 5};Task: Write a C++ function that finds and prints all pairs of indices (i, j) where arr[i] == arr[j] and i < j. Analyze the time complexity.
View Solution
#include <iostream>
using namespace std;
void findDuplicates(int arr[], int size) {
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
if (arr[i] == arr[j]) {
cout << "Duplicate: " << arr[i]
<< " at indices " << i
<< " and " << j << endl;
}
}
}
}
int main() {
int numbers[] = {5, 2, 8, 2, 9, 5};
findDuplicates(numbers, 6);
// Result: Duplicate: 5 at indices 0 and 5
// Result: Duplicate: 2 at indices 1 and 3
return 0;
}
// Time Complexity: O(n²) - nested loopsGiven:
int numbers[] = {1, 2, 3};
// Subarrays: [1], [2], [3], [1,2], [2,3], [1,2,3]Task: Write a function that calculates the sum of all possible subarrays. Return the total sum of all these subarrays.
Expected output: 20 (1 + 2 + 3 + 3 + 5 + 6)
View Solution
#include <iostream>
using namespace std;
int sumOfSubarrays(int arr[], int size) {
int totalSum = 0;
for (int start = 0; start < size; start++) {
int currentSum = 0;
for (int end = start; end < size; end++) {
currentSum += arr[end];
totalSum += currentSum;
}
}
return totalSum;
}
int main() {
int numbers[] = {1, 2, 3};
cout << sumOfSubarrays(numbers, 3) << endl;
// Result: 20 ([1]=1, [2]=2, [3]=3, [1,2]=3, [2,3]=5, [1,2,3]=6)
return 0;
}
// Time Complexity: O(n²) - nested loopsGiven:
int sorted[] = {1, 2, 3, 4, 5};
int unsorted[] = {5, 2, 8, 1, 9};Task: Implement an optimized bubble sort that stops early if no swaps occur in a pass, meaning the array is sorted. Compare the best case complexity with standard bubble sort.
View Solution
#include <iostream>
using namespace std;
void optimizedBubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
bool swapped = false;
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break; // Already sorted!
}
}
int main() {
int sorted[] = {1, 2, 3, 4, 5};
optimizedBubbleSort(sorted, 5);
// Result: Only one pass needed!
int unsorted[] = {5, 2, 8, 1, 9};
optimizedBubbleSort(unsorted, 5);
// Result: 1 2 5 8 9
return 0;
}
// Best Case: O(n) - already sorted
// Worst Case: O(n²) - reverse sortedSearching Algorithms
Searching algorithms find specific elements within data structures, a fundamental operation you'll use constantly in programming. Whether you're looking up a user in a database, finding a file on disk, or checking if a value exists in a collection, you're using a search algorithm. The two most common approaches, linear search and binary search, represent fundamentally different strategies with dramatically different performance characteristics. Understanding when to use each search method can mean the difference between code that processes data in seconds versus code that takes hours on large datasets.
Linear Search
Linear search is the simplest search algorithm: start at the beginning and check each element one by one until you find the target or reach the end. It works on any data, sorted or unsorted, making it versatile and easy to implement. The downside is that it has O(n) time complexity, meaning search time grows linearly with data size. Use linear search for small datasets (under 100 elements), unsorted data, or when you only search occasionally. For frequently searched large datasets, consider sorting the data first to enable binary search.
#include <iostream>
using namespace std;
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // Found at index i
}
}
return -1; // Not found
}
int main() {
int numbers[] = {64, 25, 12, 22, 11};
int index = linearSearch(numbers, 5, 22);
cout << "Found at index: " << index << endl; // Result: 3
index = linearSearch(numbers, 5, 99);
cout << "Found at index: " << index << endl; // Result: -1
return 0;
}This implementation demonstrates the core linear search pattern: iterate through the array sequentially, comparing each element to the target. When a match is found, return the index immediately. If the loop completes without finding the target, return -1 to indicate failure. This approach requires checking up to n elements in the worst case (when the target is at the end or not present), giving O(n) time complexity. The best case occurs when the target is the first element (O(1)), while the average case requires checking half the elements (still O(n) since we ignore constants in Big O).
Binary Search
Binary search is dramatically faster than linear search, but requires sorted data. It uses a divide-and-conquer approach: check the middle element, then eliminate half the remaining elements based on whether the target is larger or smaller. By repeatedly halving the search space, binary search achieves O(log n) time complexity. With 1 million sorted elements, linear search needs up to 1 million comparisons, while binary search needs only about 20. The trade-off is that data must be sorted first, which takes O(n log n) time. Use binary search when you have sorted data or when you'll perform many searches on the same dataset (sorting once pays off across multiple searches).
#include <iostream>
using namespace std;
int binarySearch(int arr[], int size, int target) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
int main() {
int sorted[] = {11, 12, 22, 25, 64}; // Must be sorted!
int index = binarySearch(sorted, 5, 22);
cout << "Found at index: " << index << endl; // Result: 2
return 0;
}
Binary search maintains two pointers (left and right) that define the current search range. Each iteration
calculates the middle index and compares the middle element to the target. If they match, we're done. If
the middle element is smaller than the target, the target must be in the right half, so we move left to
mid + 1. If the middle element is larger, the target must be in the left half, so we move
right to mid - 1. This halving continues until either we find the target or left surpasses
right (meaning the target doesn't exist). The calculation mid = left + (right - left) / 2
avoids integer overflow compared to (left + right) / 2.
Linear vs Binary Search Comparison
| Aspect | Linear Search | Binary Search |
|---|---|---|
| Time Complexity | O(n) | O(log n) |
| Space Complexity | O(1) | O(1) iterative, O(log n) recursive |
| Requirements | Works on any data (sorted or unsorted) | Requires sorted data |
| Best Use Cases | Small datasets (<100 elements), unsorted data, single searches | Large sorted datasets, frequent searches, performance-critical code |
Binary Search Visualization
Searching for value 22 in sorted array:
Check Middle (25)
Check Middle (12)
Found! (22)
Performance comparison: For 1,000 elements, linear search needs up to 1,000 comparisons while binary search needs only about 10 comparisons!
std::set) which maintains sorted order while
supporting O(log n) insertions, deletions, and searches.
Practice Questions
Given:
int numbers[] = {5, 2, 8, 2, 9, 2};
int target = 2;Task: Write a C++ function that finds all occurrences of a target value in an array and prints their indices.
Expected output: Found at index 1, Found at index 3, Found at index 5
View Solution
#include <iostream>
using namespace std;
void findAllOccurrences(int arr[], int size, int target) {
bool found = false;
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
cout << "Found at index " << i << endl;
found = true;
}
}
if (!found) {
cout << "Not found" << endl;
}
}
int main() {
int numbers[] = {5, 2, 8, 2, 9, 2};
findAllOccurrences(numbers, 6, 2);
// Result: Found at index 1
// Result: Found at index 3
// Result: Found at index 5
return 0;
}Given:
int arr[] = {1, 2, 2, 2, 3, 4, 5};
int target = 2;Task: Find the first and last index where target value appears using binary search for O(log n) efficiency.
Expected output: First: 1, Last: 3
View Solution
#include <iostream>
using namespace std;
int findFirst(int arr[], int size, int target) {
int left = 0, right = size - 1, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
right = mid - 1; // Continue searching left
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
int findLast(int arr[], int size, int target) {
int left = 0, right = size - 1, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
left = mid + 1; // Continue searching right
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
int main() {
int arr[] = {1, 2, 2, 2, 3, 4, 5};
int target = 2;
cout << "First: " << findFirst(arr, 7, target) << endl; // Result: 1
cout << "Last: " << findLast(arr, 7, target) << endl; // Result: 3
return 0;
}Given:
int rotated[] = {4, 5, 6, 7, 0, 1, 2}; // Originally: {0, 1, 2, 4, 5, 6, 7}
int target = 0;Task: Write a function to search for a target value in O(log n) time using modified binary search.
Expected output: 4 (index of target)
View Solution
#include <iostream>
using namespace std;
int searchRotated(int arr[], int size, int target) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[left] <= arr[mid]) { // Left half sorted
if (target >= arr[left] && target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { // Right half sorted
if (target > arr[mid] && target <= arr[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
int main() {
int rotated[] = {4, 5, 6, 7, 0, 1, 2};
cout << searchRotated(rotated, 7, 0) << endl; // Result: 4
cout << searchRotated(rotated, 7, 5) << endl; // Result: 1
return 0;
}Given:
int arr[] = {1, 2, 3, 1}; // Peak is 3 at index 2Task: A peak element is strictly greater than its neighbors. Find any peak element in O(log n) time using binary search.
Expected output: Peak at index 2 with value 3
View Solution
#include <iostream>
using namespace std;
int findPeakElement(int arr[], int size) {
int left = 0, right = size - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] > arr[mid + 1]) {
right = mid; // Peak in left half
} else {
left = mid + 1; // Peak in right half
}
}
return left; // left == right at peak
}
int main() {
int arr[] = {1, 2, 3, 1};
int peakIndex = findPeakElement(arr, 4);
cout << "Peak at index " << peakIndex; // Result: 2
cout << " with value " << arr[peakIndex] << endl; // Result: 3
return 0;
}Simple Sorting Algorithms
Simple sorting algorithms (Bubble Sort, Selection Sort, and Insertion Sort) are fundamental algorithms with O(n²) time complexity. While they are not efficient for large datasets, they are easy to understand, require minimal memory overhead, and perform well on small or nearly sorted data. These algorithms serve as excellent learning tools for understanding sorting mechanics and are practical for datasets with fewer than 50-100 elements. Understanding these algorithms builds intuition for more advanced sorting techniques like Quick Sort and Merge Sort.
Bubble Sort
Bubble Sort repeatedly steps through the array, comparing adjacent elements and swapping them if they are in the wrong order. The largest element "bubbles up" to its correct position at the end of the array with each pass. This process continues until no more swaps are needed, indicating the array is sorted. Despite its simplicity, Bubble Sort is rarely used in practice due to its poor performance on large datasets.
#include <iostream>
using namespace std;
void bubbleSort(int prices[], int size) {
for (int i = 0; i < size - 1; i++) {
bool swapped = false;
for (int j = 0; j < size - i - 1; j++) {
if (prices[j] > prices[j + 1]) {
swap(prices[j], prices[j + 1]);
swapped = true;
}
}
if (!swapped) break; // Already sorted
}
}
int main() {
int prices[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(prices) / sizeof(prices[0]);
bubbleSort(prices, size);
// Output: 11 12 22 25 34 64 90
for (int i = 0; i < size; i++) cout << prices[i] << " ";
return 0;
}
The algorithm uses two nested loops: the outer loop runs n-1 times, and the inner loop compares adjacent elements. After each pass, the largest unsorted element moves to its final position. The swapped flag optimizes the algorithm by detecting when the array becomes sorted early, allowing the algorithm to terminate. Each comparison performs at most one swap operation, moving larger elements toward the end of the array.
Best Case: O(n) when the array is already sorted (with optimization)
Average Case: O(n²) with roughly n²/2 comparisons and swaps
Worst Case: O(n²) when the array is in reverse order
Space: O(1) - sorts in place with no additional memory
Selection Sort
Selection Sort divides the array into a sorted and unsorted region. It repeatedly finds the minimum element from the unsorted region and places it at the beginning of that region. This process continues until the entire array is sorted. Unlike Bubble Sort, Selection Sort performs fewer swaps (only one per pass), making it slightly more efficient in practice for arrays where swaps are expensive operations.
#include <iostream>
using namespace std;
void selectionSort(int scores[], int size) {
for (int i = 0; i < size - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < size; j++) {
if (scores[j] < scores[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(scores[i], scores[minIndex]);
}
}
}
int main() {
int scores[] = {88, 56, 92, 45, 73, 61, 85};
int size = sizeof(scores) / sizeof(scores[0]);
selectionSort(scores, size);
// Output: 45 56 61 73 85 88 92
for (int i = 0; i < size; i++) cout << scores[i] << " ";
return 0;
}The algorithm maintains a boundary between sorted and unsorted portions of the array. In each iteration, it scans the unsorted region to find the smallest element and swaps it with the first unsorted element. This selection process guarantees exactly one swap per iteration, making the total number of swaps O(n). The algorithm is useful when write operations (swaps) are significantly more expensive than read operations (comparisons).
Best Case: O(n²) - always performs all comparisons
Average Case: O(n²) with n²/2 comparisons
Worst Case: O(n²) but with only O(n) swaps
Space: O(1) - sorts in place with constant memory
Insertion Sort
Insertion Sort builds the sorted array one element at a time by taking each element and inserting it into its correct position within the sorted portion. It works similarly to how you might sort playing cards in your hand: pick up one card at a time and insert it in the correct position. This algorithm is efficient for small datasets and performs exceptionally well on nearly sorted data, making it the best choice among simple sorting algorithms for practical use.
#include <iostream>
using namespace std;
void insertionSort(double temps[], int size) {
for (int i = 1; i < size; i++) {
double key = temps[i];
int j = i - 1;
while (j >= 0 && temps[j] > key) {
temps[j + 1] = temps[j];
j--;
}
temps[j + 1] = key;
}
}
int main() {
double temps[] = {23.5, 18.2, 31.7, 15.8, 27.3, 19.9};
int size = sizeof(temps) / sizeof(temps[0]);
insertionSort(temps, size);
// Output: 15.8 18.2 19.9 23.5 27.3 31.7
for (int i = 0; i < size; i++) cout << temps[i] << " ";
return 0;
}The algorithm starts from the second element and considers everything before it as sorted. For each element (key), it shifts all larger elements in the sorted portion one position to the right, then inserts the key into the gap created. This shifting operation is more efficient than swapping because it requires fewer assignments. Insertion Sort is adaptive (runs faster on partially sorted data) and stable (preserves the relative order of equal elements).
Best Case: O(n) when array is already sorted
Average Case: O(n²) with n²/4 comparisons on average
Worst Case: O(n²) when array is in reverse order
Space: O(1) - sorts in place with minimal overhead
Comparison of Simple Sorts
| Algorithm | Time Complexity | Space | Stable? | Best For |
|---|---|---|---|---|
| Bubble Sort | O(n²) average, O(n) best | O(1) | Yes | Educational purposes, detecting if sorted |
| Selection Sort | O(n²) all cases | O(1) | No | Minimizing number of swaps |
| Insertion Sort | O(n²) average, O(n) best | O(1) | Yes | Small or nearly sorted arrays |
A stable sort preserves the relative order of equal elements, which is crucial when sorting objects by multiple criteria. Insertion Sort often outperforms Quick Sort and Merge Sort on arrays with fewer than 10-20 elements due to lower overhead. Many advanced sorting algorithms (like Tim Sort used in Python) switch to Insertion Sort for small subarrays. For nearly sorted data, Insertion Sort's O(n) best case makes it the optimal choice. When memory is extremely constrained or when minimizing swaps is critical, these simple algorithms have practical value beyond education.
Practice Questions
Given:
double prices[] = {49.99, 29.99, 39.99, 19.99, 59.99};Task: Write a function optimizedBubbleSort that sorts the array and counts the number of swaps performed. Use the swapped flag optimization.
Expected output: Sorted array with "Swaps performed: 6"
View Solution
#include <iostream>
using namespace std;
void optimizedBubbleSort(double prices[], int size) {
int swapCount = 0;
for (int i = 0; i < size - 1; i++) {
bool swapped = false;
for (int j = 0; j < size - i - 1; j++) {
if (prices[j] > prices[j + 1]) {
swap(prices[j], prices[j + 1]);
swapped = true;
swapCount++;
}
}
if (!swapped) break;
}
cout << "Swaps performed: " << swapCount << endl;
}
int main() {
double prices[] = {49.99, 29.99, 39.99, 19.99, 59.99};
int size = sizeof(prices) / sizeof(prices[0]);
optimizedBubbleSort(prices, size);
// Output: Swaps performed: 6
for (int i = 0; i < size; i++) cout << prices[i] << " ";
// Output: 19.99 29.99 39.99 49.99 59.99
return 0;
}Given:
int empIds[] = {1005, 1002, 1008, 1001, 1006};Task: Implement Selection Sort that prints the array state after each pass, showing the boundary between sorted and unsorted regions with " | ".
Expected output: "Pass 1: 1001 | 1002 1008 1005 1006"
View Solution
#include <iostream>
using namespace std;
void selectionSortVerbose(int empIds[], int size) {
for (int i = 0; i < size - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < size; j++) {
if (empIds[j] < empIds[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(empIds[i], empIds[minIndex]);
}
// Print current state
cout << "Pass " << (i + 1) << ": ";
for (int k = 0; k <= i; k++) cout << empIds[k] << " ";
cout << "| ";
for (int k = i + 1; k < size; k++) cout << empIds[k] << " ";
cout << endl;
}
}
int main() {
int empIds[] = {1005, 1002, 1008, 1001, 1006};
selectionSortVerbose(empIds, 5);
// Pass 1: 1001 | 1002 1008 1005 1006
// Pass 2: 1001 1002 | 1008 1005 1006
// ...
return 0;
}Given:
int nearlySorted[] = {85, 88, 90, 87, 92, 95};
int reverseSorted[] = {95, 90, 85, 80, 75, 70};Task: Create an Insertion Sort that counts and returns the total number of shifts. Compare shift counts between both arrays.
Expected: Nearly sorted array has significantly fewer shifts than reverse sorted.
View Solution
#include <iostream>
using namespace std;
int insertionSortCountShifts(int scores[], int size) {
int shiftCount = 0;
for (int i = 1; i < size; i++) {
int key = scores[i];
int j = i - 1;
while (j >= 0 && scores[j] > key) {
scores[j + 1] = scores[j];
j--;
shiftCount++;
}
scores[j + 1] = key;
}
return shiftCount;
}
int main() {
int nearlySorted[] = {85, 88, 90, 87, 92, 95};
int reverseSorted[] = {95, 90, 85, 80, 75, 70};
cout << "Nearly sorted shifts: "
<< insertionSortCountShifts(nearlySorted, 6) << endl; // Result: 2
cout << "Reverse sorted shifts: "
<< insertionSortCountShifts(reverseSorted, 6) << endl; // Result: 15
return 0;
}Given:
int data[] = {64, 34, 25, 12, 22, 11, 90, 45, 50, 88};Task: Write a program comparing all three simple sorting algorithms. Track comparisons and swaps/shifts for each, then display results in a formatted table.
View Solution
#include <iostream>
#include <iomanip>
using namespace std;
struct Stats {
int comparisons;
int swaps;
};
Stats bubbleSortAnalyze(int arr[], int size) {
Stats s = {0, 0};
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
s.comparisons++;
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
s.swaps++;
}
}
}
return s;
}
Stats selectionSortAnalyze(int arr[], int size) {
Stats s = {0, 0};
for (int i = 0; i < size - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < size; j++) {
s.comparisons++;
if (arr[j] < arr[minIdx]) minIdx = j;
}
if (minIdx != i) { swap(arr[i], arr[minIdx]); s.swaps++; }
}
return s;
}
Stats insertionSortAnalyze(int arr[], int size) {
Stats s = {0, 0};
for (int i = 1; i < size; i++) {
int key = arr[i], j = i - 1;
while (j >= 0) {
s.comparisons++;
if (arr[j] > key) { arr[j + 1] = arr[j]; j--; s.swaps++; }
else break;
}
arr[j + 1] = key;
}
return s;
}
int main() {
int d1[] = {64, 34, 25, 12, 22, 11, 90, 45, 50, 88};
int d2[] = {64, 34, 25, 12, 22, 11, 90, 45, 50, 88};
int d3[] = {64, 34, 25, 12, 22, 11, 90, 45, 50, 88};
Stats bs = bubbleSortAnalyze(d1, 10);
Stats ss = selectionSortAnalyze(d2, 10);
Stats is = insertionSortAnalyze(d3, 10);
cout << left << setw(20) << "Algorithm"
<< setw(15) << "Comparisons"
<< setw(10) << "Swaps" << endl;
cout << string(45, '-') << endl;
cout << setw(20) << "Bubble Sort" << setw(15) << bs.comparisons << bs.swaps << endl;
cout << setw(20) << "Selection Sort" << setw(15) << ss.comparisons << ss.swaps << endl;
cout << setw(20) << "Insertion Sort" << setw(15) << is.comparisons << is.swaps << endl;
return 0;
}Advanced Sorting Algorithms
While simple sorting algorithms like Bubble Sort and Selection Sort work well for small datasets, they struggle with larger collections due to their O(n²) time complexity. Advanced sorting algorithms solve this problem using a divide-and-conquer strategy: break the problem into smaller subproblems, solve them recursively, and combine the results. This approach achieves O(n log n) time complexity, making these algorithms dramatically faster for large datasets. The trade-off is increased code complexity and, in some cases, additional memory usage. Understanding when to use these advanced algorithms is crucial for writing performance-critical code.
Merge Sort
Merge Sort
Merge Sort is a stable divide-and-conquer algorithm that recursively divides the array into halves until each subarray contains a single element, then merges these subarrays back together in sorted order. The key insight is that merging two sorted arrays into one sorted array can be done in linear time by comparing elements from each array and placing the smaller one into the result.
This guaranteed O(n log n) performance makes Merge Sort reliable for large datasets, though it requires O(n) extra space for the merging process.
Key characteristics: Divide-and-conquer approach, Stable sort (preserves order of equal elements), Guaranteed O(n log n) time complexity, Requires O(n) auxiliary space, Excellent for linked lists and external sorting.
#include <iostream>
using namespace std;
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
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++];
}void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
int data[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(data) / sizeof(data[0]);
mergeSort(data, 0, size - 1);
// Output: 11 12 22 25 34 64 90
for (int i = 0; i < size; i++) cout << data[i] << " ";
return 0;
}
The mergeSort function recursively divides the array by finding the midpoint and sorting each
half independently. The recursion bottoms out when subarrays contain a single element (which is inherently
sorted). The merge function then combines two sorted subarrays by creating temporary arrays,
comparing elements from each, and copying them back in sorted order. This two-step process (divide and merge)
repeats at each level of recursion. The algorithm makes log n levels of recursive calls, and each level
performs O(n) work during merging, resulting in O(n log n) total time complexity.
Best Case: O(n log n) - consistent across all inputs
Average Case: O(n log n) - always divides in half
Worst Case: O(n log n) - guaranteed performance
Space: O(n) - requires temporary arrays for merging
Quick Sort
Quick Sort is an in-place divide-and-conquer algorithm that selects a pivot element and partitions the array so that elements smaller than the pivot are on the left and larger elements are on the right. It then recursively sorts the left and right partitions. The partitioning process is the key to Quick Sort's efficiency: it rearranges elements in a single pass through the array. While Quick Sort has O(n²) worst-case time when the pivot consistently splits the array unevenly, its average-case O(n log n) performance and low memory overhead make it one of the fastest sorting algorithms in practice.
#include <iostream>
using namespace std;
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 quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
int main() {
int numbers[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(numbers) / sizeof(numbers[0]);
quickSort(numbers, 0, size - 1);
// Output: 11 12 22 25 34 64 90
for (int i = 0; i < size; i++) cout << numbers[i] << " ";
return 0;
}
The partition function chooses the last element as the pivot and rearranges the array so all
elements less than the pivot move to the left. It uses index i to track the boundary between
smaller and larger elements, swapping elements as needed. After processing all elements, it places the pivot
in its final sorted position and returns this index. The quickSort function then recursively
sorts the subarrays on either side of the pivot. This in-place partitioning eliminates the need for auxiliary
arrays, making Quick Sort more memory-efficient than Merge Sort despite similar average-case time complexity.
Best Case: O(n log n) - pivot divides array evenly
Average Case: O(n log n) - good performance in practice
Worst Case: O(n²) - already sorted data with poor pivot choice
Space: O(log n) - recursive call stack, sorts in place
Merge Sort vs Quick Sort
| Aspect | Merge Sort | Quick Sort |
|---|---|---|
| Time Complexity | O(n log n) - guaranteed all cases | O(n log n) average, O(n²) worst |
| Space | O(n) - requires temporary arrays | O(log n) - call stack only |
| Stable? | Yes - preserves element order | No - may reorder equal elements |
| Worst Case | Still O(n log n) - predictable performance | O(n²) on already sorted or reverse sorted |
| Best For | Linked lists, guaranteed performance, external sorting | Arrays, average-case speed, memory-constrained systems |
The C++ Standard Library provides
std::sort in the <algorithm> header,
which uses introsort (introspective sort). This hybrid algorithm combines Quick Sort,
Heap Sort, and Insertion Sort to get the best of all worlds: it starts with Quick Sort for its O(n log n)
average case, switches to Heap Sort if recursion depth exceeds a threshold (preventing O(n²) worst case),
and uses Insertion Sort for small subarrays (under 16 elements). This makes std::sort both
fast in practice and guaranteed O(n log n). For most applications, use std::sort rather than
implementing your own sorting algorithm. Use std::stable_sort if you need stability.
Practice Questions
Given:
int data[] = {38, 27, 43, 3, 9, 82, 10};Task: Implement Merge Sort with visualization that displays each merge operation. Add a depth parameter to track recursion level and show indentation.
View Solution
#include <iostream>
#include <string>
using namespace std;
void printArray(int arr[], int left, int right, string prefix) {
cout << prefix << "[";
for (int i = left; i <= right; i++) {
cout << arr[i];
if (i < right) cout << ", ";
}
cout << "]" << endl;
}
void merge(int arr[], int left, int mid, int right, int depth) {
string indent(depth * 2, ' ');
int n1 = mid - left + 1, n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
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++];
cout << indent << "Merged: ";
printArray(arr, left, right, "");
}
void mergeSortVisualize(int arr[], int left, int right, int depth) {
string indent(depth * 2, ' ');
if (left < right) {
cout << indent << "Dividing: ";
printArray(arr, left, right, "");
int mid = left + (right - left) / 2;
mergeSortVisualize(arr, left, mid, depth + 1);
mergeSortVisualize(arr, mid + 1, right, depth + 1);
merge(arr, left, mid, right, depth);
}
}
int main() {
int data[] = {38, 27, 43, 3, 9, 82, 10};
mergeSortVisualize(data, 0, 6, 0);
return 0;
}Given:
int sorted[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int random[] = {7, 2, 9, 4, 1, 6, 8, 3, 5, 10};Task: Implement three Quick Sort versions using different pivot selections (last, first, middle element). Compare operation counts on both arrays.
View Solution
#include <iostream>
using namespace std;
int comparisons, swaps;
int partitionLast(int arr[], int low, int high) {
int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++) {
comparisons++;
if (arr[j] < pivot) { i++; swap(arr[i], arr[j]); swaps++; }
}
swap(arr[i + 1], arr[high]); swaps++;
return i + 1;
}
int partitionMiddle(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
swap(arr[mid], arr[high]); swaps++;
return partitionLast(arr, low, high);
}
void quickSort(int arr[], int low, int high, bool useMiddle) {
if (low < high) {
int pi = useMiddle ? partitionMiddle(arr, low, high)
: partitionLast(arr, low, high);
quickSort(arr, low, pi - 1, useMiddle);
quickSort(arr, pi + 1, high, useMiddle);
}
}
int main() {
int sorted1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int sorted2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
comparisons = swaps = 0;
quickSort(sorted1, 0, 9, false); // Last pivot
cout << "Last pivot on sorted: " << comparisons << " comps, " << swaps << " swaps" << endl;
comparisons = swaps = 0;
quickSort(sorted2, 0, 9, true); // Middle pivot
cout << "Middle pivot on sorted: " << comparisons << " comps, " << swaps << " swaps" << endl;
return 0;
}Given:
const int INSERTION_THRESHOLD = 10;
int data[50]; // Random integersTask: Implement a hybrid algorithm that uses Merge Sort for large subarrays but switches to Insertion Sort when subarray size falls below threshold (10 elements).
View Solution
#include <iostream>
using namespace std;
const int INSERTION_THRESHOLD = 10;
void insertionSortRange(int arr[], int left, int right) {
for (int i = left + 1; i <= right; i++) {
int key = arr[i], j = i - 1;
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1, n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
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++];
}
void hybridSort(int arr[], int left, int right) {
if (right - left + 1 <= INSERTION_THRESHOLD) {
cout << "Using Insertion Sort for range [" << left << "-" << right << "]" << endl;
insertionSortRange(arr, left, right);
} else if (left < right) {
int mid = left + (right - left) / 2;
hybridSort(arr, left, mid);
hybridSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
int data[] = {64, 34, 25, 12, 22, 11, 90, 45, 50, 88,
7, 3, 99, 15, 42, 8, 77, 31, 56, 19};
hybridSort(data, 0, 19);
for (int i = 0; i < 20; i++) cout << data[i] << " ";
return 0;
}Given:
int duplicates[] = {5, 2, 9, 2, 8, 2, 5, 9, 2, 5, 8};Task: Implement three-way Quick Sort that partitions into: less than, equal to, and greater than pivot. This optimizes for arrays with many duplicates.
View Solution
#include <iostream>
using namespace std;
void quickSort3Way(int arr[], int low, int high) {
if (low >= high) return;
int pivot = arr[low];
int lt = low; // arr[low..lt-1] < pivot
int gt = high; // arr[gt+1..high] > pivot
int i = low + 1; // arr[lt..i-1] == pivot
while (i <= gt) {
if (arr[i] < pivot) {
swap(arr[lt++], arr[i++]);
} else if (arr[i] > pivot) {
swap(arr[i], arr[gt--]);
} else {
i++;
}
}
// arr[low..lt-1] < pivot = arr[lt..gt] < arr[gt+1..high]
cout << "Partitioned around " << pivot << ": ";
cout << "less[" << low << "-" << lt-1 << "] ";
cout << "equal[" << lt << "-" << gt << "] ";
cout << "greater[" << gt+1 << "-" << high << "]" << endl;
quickSort3Way(arr, low, lt - 1);
quickSort3Way(arr, gt + 1, high);
}
int main() {
int arr[] = {5, 2, 9, 2, 8, 2, 5, 9, 2, 5, 8};
int size = sizeof(arr) / sizeof(arr[0]);
quickSort3Way(arr, 0, size - 1);
cout << "Sorted: ";
for (int i = 0; i < size; i++) cout << arr[i] << " ";
// Output: 2 2 2 2 5 5 5 8 8 9 9
return 0;
}Choosing the Right Algorithm
Selecting the appropriate algorithm is a critical decision that directly impacts your application's performance, memory usage, and reliability. The "best" algorithm isn't determined solely by its theoretical complexity but by how well it matches your specific context: the size and nature of your data, the constraints of your environment, and the real-world requirements of your application. A simple O(n²) algorithm may outperform an O(n log n) algorithm for small datasets due to lower overhead.
Decision Factors
When choosing an algorithm, consider multiple factors that affect practical performance. The theoretical complexity provides a starting point, but real-world considerations often determine the best choice. Understanding these factors helps you make informed decisions that balance performance, memory, and maintainability.
Data Size
Small datasets (n < 100) benefit from simple algorithms. Large datasets need better asymptotic complexity.
Data State
Is data already sorted? Insertion sort excels on nearly sorted data, while others perform poorly.
Memory Constraints
In-place algorithms like quicksort use O(1) space, while merge sort requires O(n) memory.
Stability Requirement
Stable sorts preserve relative order of equal elements, critical for multi-key sorting.
Practical Recommendations
struct Employee {
string name;
double salary;
int tenure;
};
vector<Employee> staff = { /* ... */ };
// Sort by salary (descending), then by tenure
sort(staff.begin(), staff.end(),
[](const Employee& a, const Employee& b) {
if (a.salary != b.salary) return a.salary > b.salary;
return a.tenure > b.tenure; // Output: sorted staff
});
For most real-world scenarios, use the STL's std::sort() algorithm. It implements a hybrid
introsort that combines quicksort, heapsort, and insertion sort, automatically selecting the best approach
based on data characteristics. Custom comparators provide flexibility without sacrificing performance.
| Scenario | Recommended Algorithm | Reason |
|---|---|---|
| Small Data (n < 50) | Insertion Sort / Selection Sort | Simple, low overhead, fast for small inputs |
| Large Random Data | std::sort() / Quicksort |
O(n log n) average, excellent cache performance |
| Nearly Sorted Data | Insertion Sort | O(n) best case, very fast for nearly sorted |
| Need Stability | std::stable_sort() |
Preserves relative order of equal elements |
| Memory Constrained | Heap Sort / In-place Quicksort | O(1) additional space required |
Real-world Example
class ProductCatalog {
vector<Product> products;
bool isSorted = false;
Product* findProduct(int id) {
if (!isSorted && products.size() < 100) {
// Linear search for small unsorted data
for (auto& p : products)
if (p.id == id) return &p;
} else {
if (!isSorted) {
sort(products.begin(), products.end());
isSorted = true;
}
auto it = lower_bound(products.begin(), products.end(), id);
if (it != products.end() && it->id == id)
return &*it; // Output: product or nullptr
}
return nullptr;
}
};Performance Comparison
Benchmarked with n = 10,000 random integers
Avoid Premature Optimization
Start with simple, readable code using STL algorithms. Profile your application to identify actual bottlenecks before optimizing. Often, the bottleneck isn't where you expect, and premature optimization wastes time while adding complexity.
Practice Questions
Given:
vector<int> data1 = {1, 2, 3, 5, 4, 6, 7, 8, 10, 9}; // nearly sorted
vector<int> data2 = {25, 12, 8, 45, 17}; // small array
vector<int> data3 = {67, 23, 89, 12, 45, 78, 34, 56, 90, 11, ...}; // large randomTask: Implement adaptiveSort() that detects if data is nearly sorted (<10% inversions) → use Insertion Sort, small (<50) → use Selection Sort, else → use std::sort().
View Solution
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int countInversions(vector<int>& arr) {
int count = 0, n = arr.size();
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] > arr[j]) count++;
return count;
}
bool isNearlySorted(vector<int>& arr) {
int n = arr.size();
int maxInversions = n * (n - 1) / 2;
return countInversions(arr) < maxInversions * 0.1;
}
void insertionSort(vector<int>& arr) {
cout << "Using Insertion Sort (nearly sorted data)" << endl;
for (int i = 1; i < arr.size(); 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 selectionSort(vector<int>& arr) {
cout << "Using Selection Sort (small array)" << endl;
for (int i = 0; i < arr.size() - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < arr.size(); j++)
if (arr[j] < arr[minIdx]) minIdx = j;
swap(arr[i], arr[minIdx]);
}
}
void adaptiveSort(vector<int>& arr) {
if (isNearlySorted(arr)) {
insertionSort(arr);
} else if (arr.size() < 50) {
selectionSort(arr);
} else {
cout << "Using std::sort (large random data)" << endl;
sort(arr.begin(), arr.end());
}
}
int main() {
vector<int> data1 = {1, 2, 3, 5, 4, 6, 7, 8, 10, 9};
adaptiveSort(data1); // Insertion Sort
vector<int> data2 = {25, 12, 8, 45, 17};
adaptiveSort(data2); // Selection Sort
return 0;
}Given:
struct Employee { int id; string name; double salary; };
SmartCache cache;
cache.add({101, "Alice", 50000});
cache.add({102, "Bob", 55000});
cache.find(101); // multiple searchesTask: Implement SmartCache class that tracks access patterns. If searches exceed modifications by 3:1 ratio, keep data sorted and use binary search, otherwise use linear search.
View Solution
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Employee {
int id;
string name;
double salary;
bool operator<(const Employee& other) const { return id < other.id; }
};
class SmartCache {
vector<Employee> data;
bool sorted = false;
int searchCount = 0, modifyCount = 0;
void sortIfNeeded() {
if (!sorted && searchCount > modifyCount * 3) {
sort(data.begin(), data.end());
sorted = true;
cout << "Data sorted for binary search" << endl;
}
}
public:
void add(Employee emp) {
data.push_back(emp);
sorted = false;
modifyCount++;
}
Employee* find(int id) {
searchCount++;
sortIfNeeded();
if (sorted) {
cout << "Binary search for ID " << id << endl;
auto it = lower_bound(data.begin(), data.end(), Employee{id, "", 0});
if (it != data.end() && it->id == id) return &(*it);
} else {
cout << "Linear search for ID " << id << endl;
for (auto& emp : data)
if (emp.id == id) return &emp;
}
return nullptr;
}
void getStatistics() {
cout << "Searches: " << searchCount << ", Modifications: " << modifyCount;
cout << ", Mode: " << (sorted ? "Binary" : "Linear") << endl;
}
};
int main() {
SmartCache cache;
cache.add({101, "Alice", 50000});
cache.add({102, "Bob", 55000});
cache.add({103, "Charlie", 60000});
// Multiple searches trigger binary search mode
for (int i = 0; i < 10; i++) cache.find(102);
cache.getStatistics();
return 0;
}Given:
vector<int> random = generateRandom(1000);
vector<int> sorted = generateSorted(1000);
vector<int> reversed = generateReversed(1000);Task: Create benchmarking tool comparing Bubble Sort, Selection Sort, and std::sort() on random, sorted, reversed, and nearly sorted data with sizes 100, 1000, 5000. Use <chrono> for timing.
View Solution
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
#include <iomanip>
using namespace std;
using namespace chrono;
void bubbleSort(vector<int>& arr) {
for (int i = 0; i < arr.size() - 1; i++)
for (int j = 0; j < arr.size() - i - 1; j++)
if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
}
void selectionSort(vector<int>& arr) {
for (int i = 0; i < arr.size() - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < arr.size(); j++)
if (arr[j] < arr[minIdx]) minIdx = j;
swap(arr[i], arr[minIdx]);
}
}
template<typename Func>
double benchmark(Func sortFunc, vector<int> data) {
auto start = high_resolution_clock::now();
sortFunc(data);
auto end = high_resolution_clock::now();
return duration<double, milli>(end - start).count();
}
int main() {
vector<int> sizes = {100, 1000, 5000};
cout << setw(10) << "Size" << setw(15) << "Bubble"
<< setw(15) << "Selection" << setw(15) << "std::sort" << endl;
cout << string(55, '-') << endl;
for (int n : sizes) {
vector<int> data(n);
for (int i = 0; i < n; i++) data[i] = rand() % 10000;
double bubbleTime = benchmark(bubbleSort, data);
double selectTime = benchmark(selectionSort, data);
double stdTime = benchmark([](vector<int>& v){ sort(v.begin(), v.end()); }, data);
cout << setw(10) << n
<< setw(15) << fixed << setprecision(2) << bubbleTime << " ms"
<< setw(15) << selectTime << " ms"
<< setw(15) << stdTime << " ms" << endl;
}
return 0;
}Key Takeaways
Algorithm Complexity
Big O notation describes how algorithm runtime grows with input size. Understanding complexity helps you write efficient code that scales.
Binary Search
Binary search is O(log n) but requires sorted data. It eliminates half the remaining data each step, making it dramatically faster for large datasets.
Simple Sorts
Bubble, selection, and insertion sort are O(n²) but simple to implement. They work well for small datasets or nearly sorted data.
Advanced Sorts
Merge sort and quick sort achieve O(n log n) through divide-and-conquer. They are the go-to choices for large datasets.
Trade-offs
Every algorithm has trade-offs between time, space, and complexity. Choose based on your data size, structure, and performance requirements.
STL Algorithms
C++ Standard Library provides highly optimized implementations. Use std::sort, std::binary_search, and other STL algorithms in production code.
Knowledge Check
Quick Quiz
Test what you've learned about C++ algorithms