Algorithms are the backbone of computer science and play a critical role in problem-solving. However, for many students, algorithms can seem abstract and intimidating. To make students fall in love with algorithms, we must first simplify them, show their real-world applications, and offer clear examples in both pseudocode and Python.
This article walks through common algorithms, showing how they can be broken down step-by-step in pseudocode and then implemented in Python. With these examples, students will not only understand algorithms but also appreciate their elegance and efficiency.
1. Linear Search
Linear search is a simple algorithm that checks each element in a list until the target value is found or the list ends. It’s easy to understand and forms the basis for introducing students to algorithmic thinking.
Pseudocode
function linearSearch(array, target):
for each element in array:
if element == target:
return index of element
return -1Python Code
def linear_search(array, target):
for index, element in enumerate(array):
if element == target:
return index
return -1
# Example usage
arr = [5, 3, 7, 1, 9]
print(linear_search(arr, 7)) # Output: 22. Binary Search
Binary search is a more efficient algorithm used for sorted arrays. It works by repeatedly dividing the search space in half, which significantly reduces the time complexity compared to linear search.
Pseudocode
function binarySearch(array, target):
low = 0
high = length of array - 1
while low <= high:
mid = (low + high) // 2
if array[mid] == target:
return mid
else if array[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1Python Code
def binary_search(array, target):
low, high = 0, len(array) - 1
while low <= high:
mid = (low + high) // 2
if array[mid] == target:
return mid
elif array[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# Example usage
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 5)) # Output: 23. Bubble Sort
Bubble sort is a simple comparison-based sorting algorithm. While not the most efficient, it's great for teaching students the concept of sorting and how to step through elements systematically.
Pseudocode
function bubbleSort(array):
for i from 0 to length of array - 1:
for j from 0 to length of array - i - 1:
if array[j] > array[j + 1]:
swap array[j] and array[j + 1]Python Code
def bubble_sort(array):
n = len(array)
for i in range(n):
for j in range(0, n - i - 1):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # Output: [11, 12, 22, 25, 34, 64, 90]4. Selection Sort
Selection sort works by repeatedly selecting the smallest element from the unsorted portion of the array and moving it to the front. It’s a straightforward algorithm to understand, though not the most efficient for large datasets.
Pseudocode
function selectionSort(array):
for i from 0 to length of array - 1:
minIndex = i
for j from i + 1 to length of array:
if array[j] < array[minIndex]:
minIndex = j
swap array[i] and array[minIndex]Python Code
def selection_sort(array):
for i in range(len(array)):
min_index = i
for j in range(i + 1, len(array)):
if array[j] < array[min_index]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
# Example usage
arr = [29, 10, 14, 37, 13]
selection_sort(arr)
print(arr) # Output: [10, 13, 14, 29, 37]5. Merge Sort
Merge sort is a divide-and-conquer algorithm that splits the array into halves, recursively sorts them, and then merges the sorted halves. It is more efficient than bubble or selection sort, especially for large datasets.
Pseudocode
function mergeSort(array):
if length of array <= 1:
return array
mid = length of array // 2
leftHalf = mergeSort(array[0:mid])
rightHalf = mergeSort(array[mid:])
return merge(leftHalf, rightHalf)
function merge(left, right):
result = []
while left and right are not empty:
if left[0] <= right[0]:
append left[0] to result
remove left[0]
else:
append right[0] to result
remove right[0]
append remaining elements from left or right to result
return resultPython Code
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left_half = merge_sort(array[:mid])
right_half = merge_sort(array[mid:])
return merge(left_half, right_half)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr) # Output: [3, 9, 10, 27, 38, 43, 82]6. Quick Sort
Quick sort is another divide-and-conquer algorithm that works by selecting a "pivot" element and partitioning the array such that elements smaller than the pivot go to the left and larger elements go to the right. It then recursively sorts the left and right partitions.
Pseudocode
function quickSort(array):
if length of array <= 1:
return array
pivot = array[last element]
left = [elements < pivot]
right = [elements >= pivot]
return quickSort(left) + [pivot] + quickSort(right)Python Code
def quick_sort(array):
if len(array) <= 1:
return array
pivot = array[-1]
left = [x for x in array[:-1] if x < pivot]
right = [x for x in array[:-1] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
# Example usage
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quick_sort(arr)
print(sorted_arr) # Output: [1, 5, 7, 8, 9, 10]7. Dijkstra's Algorithm (Shortest Path)
Dijkstra’s algorithm finds the shortest path from a starting node to all other nodes in a weighted graph. It’s a fundamental algorithm for teaching students about graph traversal and optimization.
Pseudocode
function dijkstra(graph, source):
dist = dictionary with all nodes as keys and infinity as values
dist[source] = 0
unvisited = set of all nodes
while unvisited is not empty:
current = node in unvisited with smallest dist
unvisited.remove(current)
for neighbor in neighbors of current:
distance = dist[current] + weight of edge between current and neighbor
if distance < dist[neighbor]:
dist[neighbor] = distance
return distPython Code
import heapq
def dijkstra(graph, start):
distances = {node: float('infinity') for node in graph}
distances[start] = 0
pq = [(0, start)] # Priority queue of (distance, node)
while pq:
current_distance, current_node = heapq.heappop(pq)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
# Example usage
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)]
}
distances = dijkstra(graph, 'A')
print(distances) # Output: {'A': 0, 'B': 1, 'C': 3, 'D': 4}Conclusion
Algorithms are not just abstract concepts—they are practical tools that help us solve problems efficiently. By breaking them down into pseudocode and translating them into Python, students can better understand how these algorithms work and how they can apply them in real-world scenarios.
To make students fall in love with algorithms, we need to focus on clarity, relevance, and practice. Introducing common algorithms step by step and providing clear, real-world applications will help students appreciate their power and beauty.
