In computer science, an algorithm is a set of steps or instructions that are designed to solve a specific problem or accomplish a particular task. It is essentially a well-defined procedure that can be followed to achieve a specific goal.
Algorithms can be expressed in various forms, such as natural language, flowcharts, pseudocode, or programming languages. They can be used to perform a wide range of tasks, including sorting data, searching for information, calculating complex mathematical equations, and more.
The efficiency of an algorithm is measured by its time complexity and space complexity. Time complexity refers to how long an algorithm takes to complete its task, while space complexity refers to how much memory an algorithm requires to execute.
Algorithms are a crucial part of computer science and are used extensively in programming, software development, and other related fields. They help automate complex tasks and provide solutions to real-world problems, making them an essential tool for developers and computer scientists.
Linear Search
Binary Search
Bubble Sort
Insertion Sort
Selection Sort
Quick Sort
Merge Sort
Heap Sort
Counting Sort
Radix Sort
Bucket Sort
Depth-First Search (DFS)
Breadth-First Search (BFS)
Dijkstra’s Algorithm
Bellman-Ford Algorithm
Floyd-Warshall Algorithm
Prim’s Algorithm
Kruskal’s Algorithm
Topological Sort
Dynamic Programming
Knapsack Problem
Traveling Salesman Problem (TSP)
Convex Hull
Maximum Flow
Minimum Spanning Tree
Linear Sort
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i;
}
}
return -1; // Key not found
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 30;
int index = linearSearch(arr, n, key);
if (index != -1) {
cout << "Element found at index " << index << endl;
} else {
cout << "Element not found" << endl;
}
return 0;
}Binary Search
#include<iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
// If target is at the middle position, return mid
if (arr[mid] == target)
return mid;
// If target is greater, ignore left half
if (arr[mid] < target)
left = mid + 1;
// If target is smaller, ignore right half
else
right = mid - 1;
}
// If the target is not found, return -1
return -1;
}
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, target);
if (result == -1)
cout << "Element not found!";
else
cout << "Element found at index " << result;
return 0;
}Bubble Sort
#include <iostream>
using namespace std;
void bubbleSort(int array[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (array[j] > array[j + 1]) {
// Swap elements at positions j and j+1
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
int main() {
int array[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(array) / sizeof(array[0]);
cout << "Before sorting: ";
for (int i = 0; i < size; i++) {
cout << array[i] << " ";
}
bubbleSort(array, size);
cout << "\nAfter sorting: ";
for (int i = 0; i < size; i++) {
cout << array[i] << " ";
}
return 0;
}Insertion Sort
#include <iostream>
#include <vector>
using namespace std;
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void printArray(const vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << std::endl;
}
int main() {
vector<int> arr = { 12, 11, 13, 5, 6 };
cout << "Original array: ";
printArray(arr);
insertionSort(arr);
cout << "Sorted array: ";
printArray(arr);
return 0;
}Selection Sort
#include <iostream>
#include <vector>
using namespace std;
void selectionSort(vector<int> &arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(arr[i], arr[minIndex]);
}
}
}
int main() {
vector<int> arr = {64, 25, 12, 22, 11};
cout << "Array before sorting: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
selectionSort(arr);
cout << "Array after sorting: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
return 0;
}
Quick Sort
#include <iostream>
#include <vector>
using namespace std;
// Function to partition the array and return the pivot index
int partition(vector<int> &arr, int low, int high) {
int pivot = arr[high]; // Select the rightmost element as pivot
int i = low - 1; // Index of smaller element
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // Increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
// Function to perform the quicksort
void quickSort(vector<int> &arr, int low, int high) {
if (low < high) {
// Partitioning index
int pi = partition(arr, low, high);
// Separate recursive calls for left and right partitions
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
vector<int> arr = {64, 25, 12, 22, 11};
cout << "Array before sorting: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
int n = arr.size();
quickSort(arr, 0, n - 1);
cout << "Array after sorting: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
return 0;
}
Merge Sort
#include <iostream>
#include <vector>
using namespace std;
// Function to merge two sorted subarrays into one sorted array
void merge(vector<int> &arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
vector<int> L(n1), R(n2);
// Copy data to temporary arrays L[] and R[]
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 the temporary arrays back into arr[left..right]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
++i;
} else {
arr[k] = R[j];
++j;
}
++k;
}
// Copy the remaining elements of L[], if any
while (i < n1) {
arr[k] = L[i];
++i;
++k;
}
// Copy the remaining elements of R[], if any
while (j < n2) {
arr[k] = R[j];
++j;
++k;
}
}
// Function to implement merge sort
void mergeSort(vector<int> &arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // Calculate the middle index
// Sort first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
int main() {
vector<int> arr = {64, 25, 12, 22, 11};
cout << "Array before sorting: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
int n = arr.size();
mergeSort(arr, 0, n - 1);
cout << "Array after sorting: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
return 0;
}
Heap Sort
#include <iostream>
#include <vector>
using namespace std;
// Function to heapify a subtree rooted at index 'root' in a vector 'arr' of size 'n'
void heapify(vector<int> &arr, int n, int root) {
int largest = root; // Initialize largest as root
int left = 2 * root + 1; // Left child
int right = 2 * root + 2; // Right child
// If left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest])
largest = right;
// If largest is not root
if (largest != root) {
swap(arr[root], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to perform heap sort
void heapSort(vector<int> &arr) {
int n = arr.size();
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// Call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
int main() {
vector<int> arr = {64, 25, 12, 22, 11};
cout << "Array before sorting: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
heapSort(arr);
cout << "Array after sorting: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
return 0;
}