1.
Linear search:
• Description: A simple method that checks every element in a list
sequentially until the target value is found or the list ends.
• Algorithm:
function LinearSearch(arr, target):
for index from 0 to length(arr) - 1:
if arr[index] == target:
return index
return -1
• Output:
Input: arr = [10, 50, 30, 70, 80, 20], target = 30
Result: Element found at index 2.
2. Binary Search:
• Description: An efficient search algorithm that finds a target in a
sorted array by repeatedly dividing the search interval in half.
-
• Algorithm:
function BinarySearch(arr, target):
low = 0, high = length(arr) - 1
while low <= high:
mid = (low + high) / 2
if arr[mid] == target:
return mid
else if arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
• Output:
Input: arr = [11, 22, 33, 44, 55], target = 44
Result: Element found at index 3.
3. Quick Sort:
• Description: A divide-and-conquer algorithm that selects a 'pivot'
element and partitions the array into elements less than and greater
than the pivot.
• Algorithm:
function QuickSort(arr, low, high):
if low < high:
pi = Partition(arr, low, high)
QuickSort(arr, low, pi - 1)
QuickSort(arr, pi + 1, high)
function Partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j = low to high - 1:
if arr[j] < pivot:
i++
swap arr[i] with arr[j]
swap arr[i + 1] with arr[high]
return i + 1
• Output:
Input: [10, 7, 8, 9, 1, 5]
Result: [1, 5, 7, 8, 9, 10]
4. Merge Sort:
• Description: A divide-and-conquer algorithm that divides the array
into halves, calls itself for the two halves, and then merges the two
sorted halves.
• Algorithm:
function MergeSort(arr):
if length(arr) > 1:
mid = length(arr) / 2
L = arr[0...mid]
R = arr[mid...end]
MergeSort(L)
MergeSort(R)
Merge(arr, L, R)
function Merge(arr, L, R):
i = 0, j = 0, k = 0
nL = length(L)
nR = length(R)
// Compare elements from L and R and copy the smaller one to
arr
while i < nL and j < nR:
if L[i] <= R[j]:
arr[k] = L[i]
i=i+1
else:
arr[k] = R[j]
j=j+1
k=k+1
// Copy any remaining elements of L[]
while i < nL:
arr[k] = L[i]
i=i+1
k=k+1
// Copy any remaining elements of R[]
while j < nR:
arr[k] = R[j]
j=j+1
k=k+1
• Output:
Input: [38, 27, 43, 3, 9, 82, 10]
Result: [3, 9, 10, 27, 38, 43, 82]
5. Heap Sort:
• Description: A comparison-based sorting technique based on the
Binary Heap data structure (usually a Max-Heap).
• Algorithm:
def heapify(arr, n, i):
largest = i # Initialize largest as root
left = 2 * i + 1 # Left child index
right = 2 * i + 2 # Right child index
# Check if left child is larger than root
if left < n and arr[left] > arr[largest]:
largest = left
# Check if right child is larger than largest so far
if right < n and arr[right] > arr[largest]:
largest = right
# If largest is not root, swap them and recursively heapify the
affected subtree
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # Swap
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# Step 1: Build a max heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Step 2: Extract elements from the heap one by one
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Swap root (max) with the last
element
heapify(arr, i, 0) # Re-heapify the reduced heap
# Example usage:
arr = [12, 11, 13, 5, 6, 7]
print("Original array:", arr)
heap_sort(arr)
print("Sorted array is:", arr)
• Output:
Input: [12, 11, 13, 5, 6, 7]
Result: [5, 6, 7, 11, 12, 13]
6. Radix Sort:
• Description: A non-comparative sorting algorithm that sorts
integers by processing individual digits, from least significant to
most significant.
• Algorithm:
// Function to get the maximum value in the array
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
// Counting sort used by Radix Sort
void countingSort(int arr[], int n, int exp) {
int output[n]; // Output array
int count[10] = {0};
// Count occurrences of digits
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
// Convert count[] into cumulative count
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array (iterate backward for stability)
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
// Copy output to arr[]
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
// Radix Sort function
void radixSort(int arr[], int n) {
int max = getMax(arr, n);
// Sort by each digit (1s, 10s, 100s,...)
for (int exp = 1; max / exp > 0; exp *= 10)
countingSort(arr, n, exp);
}
// Main function to test the algorithm
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
radixSort(arr, n);
printf("\nSorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
• Output:
Input: [170 45 75 90 802 24 2 66]
Result: [2 24 45 66 75 90 170 802]
7. Counting Sort:
• Description: An integer sorting algorithm that operates by
counting the number of objects that have each distinct key value.
• Algorithm:
#include <stdio.h>
void countingSort(int arr[], int n) {
// 1. Find the maximum element
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max)
max = arr[i];
}
// 2. Create count array
int count[max + 1];
for (int i = 0; i <= max; i++)
count[i] = 0;
// 3. Store the count of each element
for (int i = 0; i < n; i++)
count[arr[i]]++;
// 4. Build the output array
int output[n];
int index = 0;
for (int i = 0; i <= max; i++) {
while (count[i] > 0) {
output[index++] = i;
count[i]--;
}
}
// 5. Copy output back to arr
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
countingSort(arr, n);
printf("\nSorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
• Output:
Input: [4 2 2 8 3 3 1]
Result: [1 2 2 3 3 4 8]
8. Insertion Sort:
• Description: Builds the final sorted array one item at a time by
picking an element and inserting it into its correct position within
the sorted part.
• Algorithm:
#include <stdio.h>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements greater than key to one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
insertionSort(arr, n);
printf("\nSorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
• Output:
Input: [12, 11, 13, 5, 6]
Result: [5, 6, 11, 12, 13]
9. Selection Sort:
• Description: Repeatedly finds the minimum element from the
unsorted part of the array and puts it at the beginning.
• Algorithm:
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
// Find the index of the minimum element
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
selectionSort(arr, n);
printf("\nSorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
• Output:
Input: [64, 25, 12, 22, 11]
Result: [11, 12, 22, 25, 64]
10. Shell Sort:
• Description: A generalized version of insertion sort that allows the
exchange of items that are far apart using a specific "gap"
sequence.
• Algorithm:
#include <stdio.h>
void shellSort(int arr[], int n) {
// Start with a big gap, then reduce the gap
for (int gap = n / 2; gap > 0; gap /= 2) {
// Perform a gapped insertion sort
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
// Shift earlier gap-sorted elements up until the correct
position is found
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
// Put temp in its correct place
arr[j] = temp;
}
}
}
int main() {
int arr[] = { 23, 29, 15, 19, 31, 7, 9, 5, 2};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
shellSort(arr, n);
printf("\nSorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
• Output:
Input: [23, 29, 15, 19, 31, 7, 9, 5, 2]
Result: [2, 5, 7, 9, 15, 19, 23, 29, 31]
11. Prim's Algorithm:
• Description: A greedy algorithm that finds a Minimum Spanning
Tree (MST) for a weighted undirected graph by growing the tree
one vertex at a time.
• Algorithm Steps:
1. Start with any vertex (usually vertex 0).
2. Mark this vertex as part of the MST.
3. Among all edges connected to the current MST set, choose the
minimum weight edge.
4. Add this edge and the new vertex to the MST.
5. Repeat until MST has V – 1 edges (V = number of vertices).
• Pseudocode:
1. Initialize key[] = ∞ for all vertices
2. key[0] = 0
3. mstSet[] = false for all
4. Repeat V-1 times:
Pick u: vertex with smallest key[] not in mstSet
mstSet[u] = true
For all adjacent vertices v:
If weight(u, v) < key[v] and v not in mstSet:
key[v] = weight(u, v)
parent[v] = u
5. parent[] will store the MST
• Output:
Input: Graph with edges (A-B: 2), (A-C: 3), (B-C: 1), (B-D: 1),
(C-D: 4)
Result: (A-B), (B-C), (B-D). Total Cost: 4.
12. Kruskal's Algorithm:
• Description: A greedy algorithm that finds an MST by sorting
edges by weight and adding them if they don't form a cycle (using
Disjoint Set).
• Algorithm Steps:
1. Sort all edges in increasing order of their weight.
2. Initialize each vertex as a separate set (Disjoint Set).
3. For each edge in sorted order:
• Check if it connects two different sets (no cycle).
• If yes → include it in MST and union the two sets.
4. Stop when MST contains V − 1 edges.
• Pseudocode:
sort edges by weight
create disjoint sets
MST = empty
for each edge (u, v):
if find(u) != find(v):
add edge to MST
union(u, v)
return MST
• Output:
Input: Graph with edges (A-B: 10), (A-C: 6), (B-C: 5), (C-D: 4)
Result: (C-D), (B-C), (A-C). Total Cost: 15.
13. Dijkstra's Algorithm:
• Description: Finds the shortest paths from a single source vertex to
all other vertices in a graph with non-negative edge weights.
• Algorithm:
function Dijkstra(graph, src):
dist[] = ∞ for all vertices
dist[src] = 0
visited[] = false for all vertices
for count = 0 to V-1:
u = vertex with minimum dist[] not visited
visited[u] = true
for each vertex v adjacent to u:
if not visited[v] and dist[u] + weight(u,v) < dist[v]:
dist[v] = dist[u] + weight(u,v)
return dist[]
• Output:
Input: Graph A->B(4), A->C(2), C->B(1), B->D(5). Source: A
Result: Shortest distances from A: A:0, B:3, C:2, D:8.
14. Bellman-Ford Algorithm:
• Description: Computes shortest paths from a single source vertex
to all other vertices, capable of handling negative weight edges.
• Algorithm:
function BellmanFord(graph, V, src):
dist[] = ∞ for all vertices
dist[src] = 0
for i = 1 to V-1:
for each edge (u, v, w):
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for each edge (u, v, w):
if dist[u] + w < dist[v]:
print "Graph contains negative weight cycle"
return dist[]
• Output:
Input: Graph A->B(-1), A->C(4), B->C(3), B->D(2), B->E(2).
Source A.
Result: Distance from A: B: -1, C: 2, D: 1, E: 1.
15. Floyd-Warshall Algorithm:
• Description: A dynamic programming algorithm for finding
shortest paths in a weighted graph with positive or negative edge
weights (but no negative cycles) between all pairs of vertices.
• Algorithm:
function FloydWarshall(graph):
dist = graph // copy graph matrix
for k = 0 to V-1:
for i = 0 to V-1:
for j = 0 to V-1:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
• Output:
Input: Matrix [[0, 3, inf], [2, 0, inf], [inf, 7, 0]] (3 nodes)
Result: Final Matrix [[0, 3, inf], [2, 0, inf], [9, 7, 0]].