Top 10 Algorithms for Beginners: Binary Search, Bubble Sort, Merge Sort, and More
If you’re new to coding, you might find yourself amidst a labyrinth of algorithms, trying to figure out where to begin. Fret not! We’ve gathered the top 10 algorithms that every beginner should know. From sorting techniques like Bubble Sort to more complex graph algorithms like Dijkstra’s, this post will help you kickstart your coding journey.
1. Binary Search: The Detective in Action
Ever wanted to feel like Sherlock Holmes, uncovering hidden clues? Binary Search is your go-to algorithm when it comes to finding an element in a sorted array. This method divides the array into halves, progressively narrowing down the search.
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, x)
print("Element is at index", str(result))If Sherlock was a programmer, this is one of the algorithms he’d use! ?️♂️
2. Bubble Sort: Bubbles Rise to the Top
As simple as it sounds, Bubble Sort compares each pair of adjacent elements and swaps them if they’re in the wrong order. Laughably inefficient for large datasets but makes sorting feel like a breeze for beginners.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Sorted array is:", sorted_arr)
A joke to lighten the mood: Why did the Bubble Sort algorithm go to therapy? Because it had too many swap issues! ?
3. Merge Sort: Divide and Conquer
Merge Sort works by dividing the unsorted list into n sublists, each containing one element, and then merging those sublists to produce a sorted list.
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr)//2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
return arr
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = merge_sort(arr)
print("Sorted array is:", sorted_arr)
4. QuickSort: The Swift Sort
QuickSort employs a divide and conquer strategy. It picks an element as the pivot and partitions the array around the picked pivot.
def partition(arr, low, high):
i = (low-1)
pivot = arr[high]
for j in range(low, high):
if arr[j] <= pivot:
i = i+1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)
return arr
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quick_sort(arr, 0, len(arr)-1)
print("Sorted array is:", sorted_arr)
5. Dijkstra’s Algorithm: The Shortest Path Finder
One of the most famous algorithms for finding the shortest paths between nodes in a graph. It’s extensively used in routing and navigation technologies.
Learn more about Dijkstra’s Algorithm here.
import sys
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
def min_distance(self, dist, spt_set):
min = sys.maxsize
for v in range(self.V):
if dist[v] < min and spt_set[v] == False:
min = dist[v]
min_index = v
return min_index
def dijkstra(self, src):
dist = [sys.maxsize] * self.V
dist[src] = 0
spt_set = [False] * self.V
for cout in range(self.V):
u = self.min_distance(dist, spt_set)
spt_set[u] = True
for v in range(self.V):
if (self.graph[u][v] > 0 and
spt_set[v] == False and
dist[v] > dist[u] + self.graph[u][v]):
dist[v] = dist[u] + self.graph[u][v]
return dist
g = Graph(9)
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]]
shortest_paths = g.dijkstra(0)
print("Vertex \t\t Distance from Source")
for node in range(len(shortest_paths)):
print(node, "\t\t", shortest_paths[node])
6. Floyd-Warshall Algorithm: All-Pairs Shortest Paths
Floyd-Warshall is another shortest path algorithm but it computes the shortest paths between all pairs of vertices in a weighted graph (with positive or negative edge weights).
V = 4
INF = 99999
def floyd_warshall(graph):
dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
for k in range(V):
for i in range(V):
for j in range(V):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
graph = [[0, 5, INF, 10],
[INF, 0, 3, INF],
[INF, INF, 0, 1],
[INF, INF, INF, 0]]
shortest_paths = floyd_warshall(graph)
print("Shortest distances between every pair of vertices")
for i in range(V):
for j in range(V):
if (shortest_paths[i][j] == INF):
print("%7s" % ("INF"), end = " ")
else:
print("%7d" % (shortest_paths[i][j]), end = " ")
if j == V-1:
print()
7. Prim’s Algorithm: Minimum Spanning Tree
Prim’s Algorithm finds the Minimum Spanning Tree for a weighted undirected graph. The concept is simple: start from a node and grow the MST one edge at a time.
import sys
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
def min_key(self, key, mst_set):
min = sys.maxsize
for v in range(self.V):
if key[v] < min and mst_set[v] == False:
min = key[v]
min_index = v
return min_index
def prim_mst(self):
key = [sys.maxsize] * self.V
parent = [None] * self.V
key[0] = 0
mst_set = [False] * self.V
parent[0] = -1
for cout in range(self.V):
u = self.min_key(key, mst_set)
mst_set[u] = True
for v in range(self.V):
if self.graph[u][v] > 0 and mst_set[v] == False and key[v] > self.graph[u][v]:
key[v] = self.graph[u][v]
parent[v] = u
return parent
8. Kruskal’s Algorithm: Another MST Algorithm
Much like Prim’s Algorithm, Kruskal’s algorithm also finds the Minimum Spanning Tree but it does so by sorting all edges and picking the smallest edge without forming a cycle.
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def kruskal_mst(self):
result = []
i = 0
e = 0
self.graph = sorted(self.graph, key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i]
i = i + 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e = e + 1
result.append([u, v, w])
self.union(parent, rank, x, y)
return result
9. Knapsack Problem: Choosing Wisely
The Knapsack Problem is a problem in combinatorial optimization. Given a set of items, each with a weight and a value, determine the number of each item to include in a collection such that the total weight is less than or equal to a given limit and the total value is as large as possible.
def knap_sack(W, wt, val, n):
if n == 0 or W == 0:
return 0
if (wt[n-1] > W):
return knap_sack(W, wt, val, n-1)
else:
return max(val[n-1] + knap_sack(W-wt[n-1], wt, val, n-1),
knap_sack(W, wt, val, n-1))
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knap_sack(W, wt, val, n))
10. Tower of Hanoi: The Classic Puzzle
The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes which can slide onto any rod.
def tower_of_hanoi(n, from_rod, to_rod, aux_rod):
if n == 0:
return
tower_of_hanoi(n-1, from_rod, aux_rod, to_rod)
print("Move disk", n, "from rod", from_rod, "to rod", to_rod)
tower_of_hanoi(n-1, aux_rod, to_rod, from_rod)
n = 4
tower_of_hanoi(n, 'A', 'C', 'B')
Hope you enjoyed both the learning and the jokes! ?