Algorithms are step-by-step procedures to solve a problem efficiently. In C++ development, algorithms are used for searching, sorting, optimization, graph traversal, scheduling, and system design. The C++ Standard Template Library (STL) also provides many ready-made algorithms in the <algorithm> header.
Below is a structured overview of algorithms important for C++ developers. 🚀
1️⃣ What is an Algorithm
An algorithm is a sequence of instructions to solve a specific problem.
Example problem:
Find a number in a list.
Possible algorithm:
1. Start from first element
2. Compare with target
3. Move to next element
4. Repeat until found
2️⃣ Characteristics of Good Algorithms
| Property | Meaning |
|---|---|
| Input | Takes zero or more inputs |
| Output | Produces result |
| Definiteness | Clear steps |
| Finiteness | Must terminate |
| Efficiency | Uses minimal time and memory |
3️⃣ Algorithm Complexity (Big-O)
Algorithms are evaluated using time complexity.
| Complexity | Meaning |
|---|---|
| O(1) | Constant time |
| O(log n) | Logarithmic |
| O(n) | Linear |
| O(n log n) | Efficient sorting |
| O(n²) | Slow for large data |
Example:
n = 1000O(n) → 1000 operations
O(n²) → 1,000,000 operations
4️⃣ Sorting Algorithms
Sorting arranges data in ascending or descending order.
Bubble Sort
Idea: repeatedly swap adjacent elements.
Example:
#include <iostream>
using namespace std;void bubbleSort(int arr[], int n)
{
for(int i=0;i<n-1;i++)
for(int j=0;j<n-i-1;j++)
if(arr[j] > arr[j+1])
swap(arr[j],arr[j+1]);
}int main()
{
int arr[] = {5,2,8,1}; bubbleSort(arr,4); for(int x:arr)
cout<<x<<" ";
}
Complexity:
O(n²)
Quick Sort (Very Important)
Used in many real systems.
Idea:
- Choose pivot
- Partition array
- Recursively sort parts
#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 pi = partition(arr, low, high); quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}
Complexity:
Average → O(n log n)
Worst → O(n²)
5️⃣ Searching Algorithms
Linear Search
int linearSearch(int arr[], int n, int key)
{
for(int i=0;i<n;i++)
if(arr[i]==key)
return i; return -1;
}
Complexity:
O(n)
Binary Search
Works only on sorted arrays.
int binarySearch(int arr[], int l, int r, int key)
{
while(l <= r)
{
int mid = (l+r)/2; if(arr[mid] == key)
return mid; if(arr[mid] < key)
l = mid + 1;
else
r = mid - 1;
} return -1;
}
Complexity:
O(log n)
6️⃣ STL Algorithms in C++
C++ provides powerful built-in algorithms.
Header:
#include <algorithm>
Sort
#include <algorithm>sort(v.begin(), v.end());
Example:
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;int main()
{
vector<int> v = {5,2,9,1}; sort(v.begin(), v.end()); for(int x:v)
cout<<x<<" ";
}
Find
auto it = find(v.begin(), v.end(), 5);
Reverse
reverse(v.begin(), v.end());
Count
count(v.begin(), v.end(), 5);
7️⃣ Graph Algorithms
Used in:
- networking
- GPS
- social networks
Breadth First Search (BFS)
Uses queue.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;void BFS(int start, vector<int> graph[])
{
bool visited[10] = {false}; queue<int> q; q.push(start);
visited[start] = true; while(!q.empty())
{
int node = q.front();
q.pop(); cout<<node<<" "; for(int next:graph[node])
{
if(!visited[next])
{
visited[next] = true;
q.push(next);
}
}
}
}
Depth First Search (DFS)
Uses recursion or stack.
void DFS(int node, vector<int> graph[], bool visited[])
{
visited[node] = true; cout<<node<<" "; for(int next : graph[node])
if(!visited[next])
DFS(next,graph,visited);
}
8️⃣ Dynamic Programming
Used for optimization problems.
Example: Fibonacci.
Normal recursion:
O(2^n)
DP version:
int fib(int n)
{
int dp[n+1]; dp[0]=0;
dp[1]=1; for(int i=2;i<=n;i++)
dp[i]=dp[i-1]+dp[i-2]; return dp[n];
}
Complexity:
O(n)
9️⃣ Greedy Algorithms
Make locally optimal choices.
Example:
- coin change
- scheduling
- minimum spanning tree
🔟 Recursion
Function calls itself.
Example factorial:
int factorial(int n)
{
if(n==0)
return 1; return n * factorial(n-1);
}
Most Important Algorithms for C++ Developers
| Category | Algorithms |
|---|---|
| Sorting | Quick Sort, Merge Sort |
| Searching | Binary Search |
| Graph | BFS, DFS |
| Optimization | Dynamic Programming |
| Greedy | Dijkstra, Prim |
| String | KMP |
Algorithms Used in Real Systems
| System | Algorithm |
|---|---|
| Google search | Graph algorithms |
| Database index | B-Tree |
| Compression | Huffman coding |
| Routing | Dijkstra algorithm |
| Compiler | Parsing algorithms |
✅ Key takeaway
For serious C++ development you should master:
1️⃣ Sorting algorithms
2️⃣ Searching algorithms
3️⃣ Graph algorithms
4️⃣ Dynamic programming
5️⃣ STL algorithms