Essential Algorithms in Python
Bubble Sort
A straightforward comparison-based sorting technique that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
def bubble_sort(data):
size = len(data)
for i in range(size):
for j in range(size - i - 1):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
# Example
bubble_sort([64, 34, 25, 12, 22, 11, 90])
Selection Sort
This algorithm divides the input into sorted and unsorted regions, repeatedly selecting the smallest element from the unsorted portion and moving it to the sorted end.
def selection_sort(data):
for i in range(len(data)):
min_index = i
for j in range(i + 1, len(data)):
if data[j] < data[min_index]:
min_index = j
data[i], data[min_index] = data[min_index], data[i]
# Example
selection_sort([64, 25, 12, 22, 11])
Insertion Sort
A simple algorithm that builds the final sorted array one item at a time, inserting each new element into its correct position within the already-sorted portion.
def insertion_sort(data):
for i in range(1, len(data)):
current = data[i]
j = i - 1
while j >= 0 and current < data[j]:
data[j + 1] = data[j]
j -= 1
data[j + 1] = current
# Example
insertion_sort([12, 11, 13, 5, 6])
Quick Sort
A divide-and-conquer algorithm that selects a pivot element and partitions the array around it, placing smaller elements to the left and larger elements to the right, then recursively sorting the sub-arrays.
def quick_sort(collection):
if len(collection) <= 1:
return collection
pivot_index = len(collection) // 2
pivot_value = collection[pivot_index]
left = [item for item in collection if item < pivot_value]
center = [item for item in collection if item == pivot_value]
right = [item for item in collection if item > pivot_value]
return quick_sort(left) + center + quick_sort(right)
# Example
quick_sort([3, 6, 8, 10, 1, 2, 1])
Merge Sort
A divide-and-conquer approach that recursively divides the array into halves until single elements remain, then merges them back together in sorted order.
def merge_sort(collection):
if len(collection) > 1:
middle = len(collection) // 2
left_part = collection[:middle]
right_part = collection[middle:]
merge_sort(left_part)
merge_sort(right_part)
i = j = k = 0
while i < len(left_part) and j < len(right_part):
if left_part[i] <= right_part[j]:
collection[k] = left_part[i]
i += 1
else:
collection[k] = right_part[j]
j += 1
k += 1
while i < len(left_part):
collection[k] = left_part[i]
i += 1
k += 1
while j < len(right_part):
collection[k] = right_part[j]
j += 1
k += 1
# Example
merge_sort([12, 11, 13, 5, 6, 7])
Heap Sort
A comparison-based algorithm that uses a binary heap data structure, covnerting the array into a max heap and then repeatedly extracting the maximum element.
def heapify(sequence, heap_size, root_index):
largest = root_index
left_child = 2 * root_index + 1
right_child = 2 * root_index + 2
if left_child < heap_size and sequence[root_index] < sequence[left_child]:
largest = left_child
if right_child < heap_size and sequence[largest] < sequence[right_child]:
largest = right_child
if largest != root_index:
sequence[root_index], sequence[largest] = sequence[largest], sequence[root_index]
heapify(sequence, heap_size, largest)
def heap_sort(sequence):
n = len(sequence)
for i in range(n // 2 - 1, -1, -1):
heapify(sequence, n, i)
for i in range(n - 1, 0, -1):
sequence[0], sequence[i] = sequence[i], sequence[0]
heapify(sequence, i, 0)
# Example
heap_sort([12, 11, 13, 5, 6, 7])
Counting Sort
An integer sorting algorithm that works by counting the number of objects having distinct key values, suitable for a limited range of integers.
def counting_sort(sequence):
maximum = max(sequence)
counter = [0] * (maximum + 1)
for value in sequence:
counter[value] += 1
index = 0
for value in range(maximum + 1):
while counter[value] > 0:
sequence[index] = value
index += 1
counter[value] -= 1
# Example
counting_sort([4, 2, 2, 8, 3, 3, 1])
Radix Sort
A non-comparison integer sorting algorithm that processes digits from least significant to most significant, using counting sort as a subroutine.
def counting_sort_by_digit(sequence, digit_place):
size = len(sequence)
result = [0] * size
counter = [0] * 10
for i in range(size):
digit = (sequence[i] // digit_place) % 10
counter[digit] += 1
for i in range(1, 10):
counter[i] += counter[i - 1]
i = size - 1
while i >= 0:
digit = (sequence[i] // digit_place) % 10
result[counter[digit] - 1] = sequence[i]
counter[digit] -= 1
i -= 1
for i in range(size):
sequence[i] = result[i]
def radix_sort(sequence):
maximum = max(sequence)
digit_place = 1
while maximum // digit_place > 0:
counting_sort_by_digit(sequence, digit_place)
digit_place *= 10
# Example
radix_sort([170, 45, 75, 90, 802, 24, 2, 66])
Bucket Sort
A distribution-based sorting algorithm that distributes elements into a number of buckets, sorts each bucket individually, and then concatenates the results.
def bucket_sort(sequence):
bucket_count = len(sequence)
buckets = [[] for _ in range(bucket_count)]
for value in sequence:
bucket_index = int(bucket_count * value)
buckets[bucket_index].append(value)
for i in range(bucket_count):
buckets[i] = sorted(buckets[i])
index = 0
for bucket in buckets:
for value in bucket:
sequence[index] = value
index += 1
# Example
bucket_sort([0.897, 0.565, 0.656, 0.123, 0.665, 0.343])
Shell Sort
An optimization of insertion sort that allows the exchange of items that are far apart, using decreasing gaps to improve efficiency.
def shell_sort(sequence):
n = len(sequence)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = sequence[i]
j = i
while j >= gap and sequence[j - gap] > temp:
sequence[j] = sequence[j - gap]
j -= gap
sequence[j] = temp
gap //= 2
# Example
shell_sort([12, 34, 54, 2, 3])
Binary Search
An efficient algorithm for finding an item in a sorted array by repeatedly dividing the search interval in half.
def binary_search(sorted_list, target):
left = 0
right = len(sorted_list) - 1
while left <= right:
mid = left + (right - left) // 2
if sorted_list[mid] == target:
return mid
elif sorted_list[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Example
data = [2, 3, 4, 10, 40]
target = 10
binary_search(data, target)
Linear Search
The simplest search algorithm that checks every element in the list sequentially until the target is found or the list ends.
def linear_search(sequence, target):
for idx in range(len(sequence)):
if sequence[idx] == target:
return idx
return -1
# Example
data = [2, 3, 4, 10, 40]
target = 10
linear_search(data, target)
Breadth-First Search (BFS)
A graph traversal algorithm that explores all vertices at the current depth before moving to vertices at the next depth level.
from collections import deque
def bfs(graph, start_node):
visited = set()
queue = deque([start_node])
visited.add(start_node)
while queue:
current = queue.popleft()
print(current, end=" ")
for neighbor in graph[current]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Example
graph = {
'A': ['B', 'C', 'D'],
'B': ['E', 'F'],
'C': ['G'],
'D': [],
'E': [],
'F': [],
'G': []
}
bfs(graph, 'A')
Depth-First Search (DFS)
A graph traversal algorithm that explores as far as possible along each branch before backtracking.
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=" ")
for next_node in graph[node] - visited:
dfs(graph, next_node, visited)
# Example
graph = {
'A': {'B', 'C'},
'B': {'A', 'D', 'E'},
'C': {'A', 'F'},
'D': {'B'},
'E': {'B', 'F'},
'F': {'C', 'E'}
}
dfs(graph, 'A')
Dijkstra's Algorithm
A shortest path algorithm that finds the minimum distance from a single source vertex to all other vertices in a weighted graph.
import sys
def dijkstra(graph, source):
distances = {source: (None, 0)}
current = source
visited = set()
while current is not None:
visited.add(current)
neighbors = graph[current]
current_distance = distances[current][1]
for neighbor, weight in neighbors.items():
total_distance = current_distance + weight
if neighbor not in distances:
distances[neighbor] = (current, total_distance)
else:
existing_distance = distances[neighbor][1]
if existing_distance > total_distance:
distances[neighbor] = (current, total_distance)
unvisited = {v: distances[v] for v in distances if v not in visited}
if not unvisited:
break
current = min(unvisited, key=lambda k: unvisited[k][1])
return distances
# Example
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
dijkstra(graph, 'A')
A* Algorithm
A best-first search algorithm that finds the shortest path using heuristics to guide the search, combining actual cost and estimated cost to the goal.
from queue import PriorityQueue
def manhattan_distance(point_a, point_b):
return abs(point_b[0] - point_a[0]) + abs(point_b[1] - point_a[1])
def a_star_search(graph, start, goal):
frontier = PriorityQueue()
frontier.put((0, start))
came_from = {start: None}
cost_accumulated = {start: 0}
while not frontier.empty():
current = frontier.get()[1]
if current == goal:
break
for next_node in graph[current]:
new_g = cost_accumulated[current] + graph[current][next_node]
if next_node not in cost_accumulated or new_g < cost_accumulated[next_node]:
cost_accumulated[next_node] = new_g
f_score = new_g + manhattan_distance(goal, next_node)
frontier.put((f_score, next_node))
came_from[next_node] = current
return came_from, cost_accumulated
# Example
graph = {
'A': {'B': 1, 'C': 3},
'B': {'A': 1, 'C': 1, 'D': 6},
'C': {'A': 3, 'B': 1, 'D': 2, 'E': 4},
'D': {'B': 6, 'C': 2, 'E': 1},
'E': {'C': 4, 'D': 1}
}
a_star_search(graph, 'A', 'E')
Topological Sort
An algorithm that produces a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge, the source vertex comes before the destination.
from collections import defaultdict
def topological_util(vertex, visited, stack, adjacency):
visited[vertex] = True
for neighbor in adjacency[vertex]:
if not visited[neighbor]:
topological_util(neighbor, visited, stack, adjacency)
stack.insert(0, vertex)
def topological_sort(adjacency):
visited = {v: False for v in adjacency}
stack = []
for vertex in adjacency:
if not visited[vertex]:
topological_util(vertex, visited, stack, adjacency)
return stack
# Example
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
topological_sort(graph)
Kruskal's Algorithm
An algorithm for finding a minimum spanning tree in a weighted undirected graph by sorting edges and adding them if they don't create a cycle.
class MinimumSpanningTree:
def __init__(self, vertex_count):
self.vertex_count = vertex_count
self.edges = []
def add_edge(self, u, v, weight):
self.edges.append([u, v, weight])
def find_parent(self, parent, node):
if parent[node] == node:
return node
return self.find_parent(parent, parent[node])
def union_sets(self, parent, rank, x, y):
root_x = self.find_parent(parent, x)
root_y = self.find_parent(parent, y)
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] += 1
def kruskal_mst(self):
result = []
edge_index = 0
edge_count = 0
self.edges = sorted(self.edges, key=lambda e: e[2])
parent = list(range(self.vertex_count))
rank = [0] * self.vertex_count
while edge_count < self.vertex_count - 1:
u, v, w = self.edges[edge_index]
edge_index += 1
parent_u = self.find_parent(parent, u)
parent_v = self.find_parent(parent, v)
if parent_u != parent_v:
edge_count += 1
result.append([u, v, w])
self.union_sets(parent, rank, parent_u, parent_v)
return result
# Example
g = MinimumSpanningTree(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
g.kruskal_mst()
Prim's Algorithm
Another minimum spanning tree algorithm that grows the tree by adding the cheapest edge from a visited vertex to an unvisited vertex.
import sys
def find_min_key(keys, included, vertices):
min_val = sys.maxsize
for v in range(vertices):
if not included[v] and keys[v] < min_val:
min_val = keys[v]
min_index = v
return min_index
def prim_mst(graph, vertices):
keys = [sys.maxsize] * vertices
parent = [None] * vertices
keys[0] = 0
included = [False] * vertices
parent[0] = -1
for _ in range(vertices):
u = find_min_key(keys, included, vertices)
included[u] = True
for v in range(vertices):
if graph[u][v] and not included[v] and graph[u][v] < keys[v]:
keys[v] = graph[u][v]
parent[v] = u
return parent
# Example
adj_matrix = [
[0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]
]
prim_mst(adj_matrix, 5)
Floyd-Warshall Algorithm
An algorithm for finding shortest paths between all pairs of vertices in a weighted graph.
def floyd_warshall(graph):
distance = [row[:] for row in graph]
n = len(graph)
for k in range(n):
for i in range(n):
for j in range(n):
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
return distance
# Example
INF = float('inf')
graph = [
[0, 5, INF, 10],
[INF, 0, 3, INF],
[INF, INF, 0, 1],
[INF, INF, INF, 0]
]
floyd_warshall(graph)
Bellman-Ford Algorithm
An algorithm that computes shortest paths from a single source vertex to all other vertices, capable of handling negative weights.
def bellman_ford(edges, vertex_count, edge_count, source):
distances = [float("Inf")] * vertex_count
distances[source] = 0
for _ in range(vertex_count - 1):
for u, v, w in edges:
if distances[u] != float("Inf") and distances[u] + w < distances[v]:
distances[v] = distances[u] + w
for u, v, w in edges:
if distances[u] != float("Inf") and distances[u] + w < distances[v]:
print("Negative cycle detected")
return None
return distances
# Example
V = 5
edges = [
[0, 1, -1],
[0, 2, 4],
[1, 2, 3],
[1, 3, 2],
[1, 4, 2],
[3, 2, 5],
[3, 1, 1],
[4, 3, -3]
]
bellman_ford(edges, V, len(edges), 0)
Kadane's Algorithm
An algorithm for finding the maximum sum of a contiguous subarray in a one-dimensional array.
def kadane(array):
max_total = array[0]
current_max = array[0]
for i in range(1, len(array)):
current_max = max(array[i], current_max + array[i])
max_total = max(max_total, current_max)
return max_total
# Example
kadane([1, -3, 2, 1, -1])
Longest Common Subsequence (LCS)
An algorithm for finding the longest subsequence common to two sequences.
def lcs(sequence_x, sequence_y):
m = len(sequence_x)
n = len(sequence_y)
dp_table = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
dp_table[i][j] = 0
elif sequence_x[i - 1] == sequence_y[j - 1]:
dp_table[i][j] = dp_table[i - 1][j - 1] + 1
else:
dp_table[i][j] = max(dp_table[i - 1][j], dp_table[i][j - 1])
return dp_table[m][n]
# Example
X = "AGGTAB"
Y = "GXTXAYB"
lcs(X, Y)
Edit Distance
An algorithm that computes the minimum number of operations required to transform one string into another through insertions, deletions, or substitutions.
def edit_distance(string1, string2):
m, n = len(string1), len(string2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif string1[i - 1] == string2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
return dp[m][n]
# Example
edit_distance("sunday", "saturday")
0/1 Knapsack Problem
A combinatorial optimizaton problem where items with weights and values must be selected to maximize value without exceeding capacity.
def knapsack(capacity, weights, values, item_count):
dp = [[0] * (capacity + 1) for _ in range(item_count + 1)]
for i in range(item_count + 1):
for w in range(capacity + 1):
if i == 0 or w == 0:
dp[i][w] = 0
elif weights[i - 1] <= w:
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
else:
dp[i][w] = dp[i - 1][w]
return dp[item_count][capacity]
# Example
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
knapsack(capacity, weights, values, len(values))
Longest Increasing Subsequence (LIS)
An algorithm for finding the longest subsequence where elements are in strictly increasing order.
def lis(sequence):
n = len(sequence)
lengths = [1] * n
for i in range(1, n):
for j in range(i):
if sequence[i] > sequence[j] and lengths[i] < lengths[j] + 1:
lengths[i] = lengths[j] + 1
return max(lengths)
# Example
lis([10, 22, 9, 33, 21, 50, 41, 60, 80])
Tower of Hanoi
A classic mathematical puzzle involving moving a stack of disks between pegs under specific rules.
def tower_of_hanoi(n, source, destination, auxiliary):
if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return
tower_of_hanoi(n - 1, source, auxiliary, destination)
print(f"Move disk {n} from {source} to {destination}")
tower_of_hanoi(n - 1, auxiliary, destination, source)
# Example
tower_of_hanoi(4, 'A', 'C', 'B')
N-Queens Problem
A puzzle that involves placing N chess queens on an N×N board so that no two queens threaten each other.
def display_board(board):
for row in board:
print(" ".join(str(cell) for cell in row))
def is_valid_position(board, row, col, size):
for i in range(col):
if board[row][i] == 1:
return False
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
for i, j in zip(range(row, size), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
def solve_queens(board, col, size):
if col >= size:
return True
for row in range(size):
if is_valid_position(board, row, col, size):
board[row][col] = 1
if solve_queens(board, col + 1, size):
return True
board[row][col] = 0
return False
def n_queens(size):
board = [[0] * size for _ in range(size)]
if not solve_queens(board, 0, size):
print("No solution exists")
return False
display_board(board)
return True
# Example
n_queens(4)
Rat in a Maze
A backtracking problem that finds all possible paths for a rat to reach the exit from the starting position in a maze.
def is_safe(maze, x, y, size):
return 0 <= x < size and 0 <= y < size and maze[x][y] == 1
def solve_maze_recursive(maze, x, y, solution, size):
if x == size - 1 and y == size - 1 and maze[x][y] == 1:
solution[x][y] = 1
return True
if is_safe(maze, x, y, size):
if solution[x][y] == 1:
return False
solution[x][y] = 1
if solve_maze_recursive(maze, x + 1, y, solution, size):
return True
if solve_maze_recursive(maze, x, y + 1, solution, size):
return True
if solve_maze_recursive(maze, x - 1, y, solution, size):
return True
if solve_maze_recursive(maze, x, y - 1, solution, size):
return True
solution[x][y] = 0
return False
def solve_maze(maze):
size = len(maze)
solution = [[0] * size for _ in range(size)]
if not solve_maze_recursive(maze, 0, 0, solution, size):
print("No path found")
return False
display_board(solution)
return True
# Example
maze = [
[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]
]
solve_maze(maze)
Graph Coloring Problem
A constraint satisfaction problem that assigns colors to vertices of a graph such that no two adjacent vertices share the same color.
def can_color(vertex, graph, colors, color):
for neighbor in range(len(graph)):
if graph[vertex][neighbor] == 1 and colors[neighbor] == color:
return False
return True
def color_graph_recursive(graph, color_count, colors, vertex):
if vertex == len(graph):
return True
for c in range(1, color_count + 1):
if can_color(vertex, graph, colors, c):
colors[vertex] = c
if color_graph_recursive(graph, color_count, colors, vertex + 1):
return True
colors[vertex] = 0
def graph_coloring(graph, color_count):
colors = [0] * len(graph)
if not color_graph_recursive(graph, color_count, colors, 0):
print("No valid coloring exists")
return False
print("Valid coloring:", colors)
return True
# Example
graph = [
[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0]
]
graph_coloring(graph, 3)
Josephus Problem
A mathematical problem where people stand in a circle and every k-th person is eliminated until only one remains.
def josephus(n, k):
if n == 1:
return 0
return (josephus(n - 1, k) + k) % n
# Example
josephus(7, 3)
Partition Problem
A problem that determines whether a set can be divided into two subsets with equal sum.
def can_form_subset(arr, count, target_sum):
subset = [[False] * (target_sum + 1) for _ in range(count + 1)]
for i in range(count + 1):
subset[i][0] = True
for i in range(1, count + 1):
for j in range(1, target_sum + 1):
if j < arr[i - 1]:
subset[i][j] = subset[i - 1][j]
else:
subset[i][j] = subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]
return subset[count][target_sum]
def can_partition(arr):
total = sum(arr)
if total % 2 != 0:
return False
return can_form_subset(arr, len(arr), total // 2)
# Example
arr = [3, 1, 5, 9, 12]
can_partition(arr)
KMP Algorithm
A string matching algorithm that searches for occurrences of a pattern within a text using prefix function to avoid redundant comparisons.
def build_lps(pattern, pattern_length):
lps = [0] * pattern_length
length = 0
i = 1
while i < pattern_length:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
def kmp_search(text, pattern):
text_length = len(text)
pattern_length = len(pattern)
lps = build_lps(pattern, pattern_length)
i = j = 0
while i < text_length:
if pattern[j] == text[i]:
i += 1
j += 1
elif j == pattern_length:
print(f"Pattern found at index {i - j}")
j = lps[j - 1]
elif i < text_length and pattern[j] != text[i]:
if j != 0:
j = lps[j - 1]
else:
i += 1
# Example
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
kmp_search(text, pattern)
