WikiGalaxy
C++ Algorithms: Sorting
Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
#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[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Console Output:
Sorted array: 11 12 22 25 34 64 90
C++ Algorithms: Searching
Binary Search
Binary Search is an efficient algorithm for finding an item from a sorted list of items, by repeatedly dividing the search interval in half.
#include <iostream>
using namespace std;
int binarySearch(int arr[], int l, int r, int x) {
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n-1, x);
if(result == -1)
cout << "Element not present in array";
else
cout << "Element found at index " << result;
return 0;
}
Console Output:
Element found at index 3
C++ Algorithms: Graphs
Depth First Search (DFS)
Depth First Search is an algorithm for traversing or searching tree or graph data structures, starting at the root and exploring as far as possible along each branch before backtracking.
#include <iostream>
#include <list>
using namespace std;
class Graph {
int V;
list *adj;
void DFSUtil(int v, bool visited[]);
public:
Graph(int V);
void addEdge(int v, int w);
void DFS(int v);
};
Graph::Graph(int V) {
this->V = V;
adj = new list[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::DFSUtil(int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
for (auto i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
void Graph::DFS(int v) {
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
DFSUtil(v, visited);
}
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Depth First Traversal (starting from vertex 2): ";
g.DFS(2);
return 0;
}
Console Output:
Depth First Traversal (starting from vertex 2): 2 0 1 3
C++ Algorithms: Dynamic Programming
Fibonacci Series with Memoization
Dynamic Programming approach to compute Fibonacci numbers using memoization to store previously computed values for faster access.
#include <iostream>
using namespace std;
int fib(int n, int memo[]) {
if (n <= 1)
return n;
if (memo[n] == 0)
memo[n] = fib(n-1, memo) + fib(n-2, memo);
return memo[n];
}
int main() {
int n = 10;
int memo[n+1] = {0};
cout << "Fibonacci number is " << fib(n, memo);
return 0;
}
Console Output:
Fibonacci number is 55
C++ Algorithms: Data Structures
Linked List Insertion
A linked list is a linear data structure where each element is a separate object, with each element (node) comprising a data part and a reference (link) to the next node in the sequence.
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};
void push(Node** head_ref, int new_data) {
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(Node* node) {
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
int main() {
Node* head = NULL;
push(&head, 1);
push(&head, 2);
push(&head, 3);
cout << "Created Linked list is: ";
printList(head);
return 0;
}
Console Output:
Created Linked list is: 3 2 1
C++ Algorithms: Recursion
Factorial Calculation
Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. Factorial calculation is a classic example of recursion.
#include <iostream>
using namespace std;
int factorial(int n) {
if (n <= 1)
return 1;
else
return n * factorial(n - 1);
}
int main() {
int num = 5;
cout << "Factorial of " << num << " is " << factorial(num);
return 0;
}
Console Output:
Factorial of 5 is 120
C++ Algorithms: Backtracking
N-Queens Problem
The N-Queens problem is a classic backtracking problem where the goal is to place N queens on an N×N chessboard so that no two queens threaten each other.
#include <iostream>
#define N 4
using namespace std;
void printSolution(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << board[i][j] << " ";
cout << endl;
}
}
bool isSafe(int board[N][N], int row, int col) {
for (int i = 0; i < col; i++)
if (board[row][i])
return false;
for (int i=row, j=col; i>=0 && j>=0; i--, j--)
if (board[i][j])
return false;
for (int i=row, j=col; j>=0 && i<N; i++, j--)
if (board[i][j])
return false;
return true;
}
bool solveNQUtil(int board[N][N], int col) {
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
board[i][col] = 0;
}
}
return false;
}
bool solveNQ() {
int board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (solveNQUtil(board, 0) == false) {
cout << "Solution does not exist";
return false;
}
printSolution(board);
return true;
}
int main() {
solveNQ();
return 0;
}
Console Output:
1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0
C++ Algorithms: Greedy
Activity Selection
The Activity Selection problem is a classic problem of Greedy algorithms where the goal is to select the maximum number of activities that don't overlap.
#include <iostream>
#include <algorithm>
using namespace std;
struct Activity {
int start, finish;
};
bool activityCompare(Activity s1, Activity s2) {
return (s1.finish < s2.finish);
}
void printMaxActivities(Activity arr[], int n) {
sort(arr, arr+n, activityCompare);
cout << "Selected activities: ";
int i = 0;
cout << "(" << arr[i].start << ", " << arr[i].finish << ")";
for (int j = 1; j < n; j++) {
if (arr[j].start >= arr[i].finish) {
cout << ", (" << arr[j].start << ", " << arr[j].finish << ")";
i = j;
}
}
}
int main() {
Activity arr[] = {{5, 9}, {1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}};
int n = sizeof(arr)/sizeof(arr[0]);
printMaxActivities(arr, n);
return 0;
}
Console Output:
Selected activities: (1, 2), (3, 4), (5, 7), (8, 9)
C++ Algorithms: Divide and Conquer
Merge Sort
Merge Sort is a Divide and Conquer algorithm that divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);
mergeSort(arr, 0, arr_size - 1);
cout << "Sorted array: ";
for (int i = 0; i < arr_size; i++)
cout << arr[i] << " ";
return 0;
}
Console Output:
Sorted array: 5 6 7 11 12 13
