Essential Algorithms and Their Python Implementations
- Bubble Sort
def organize_with_bubble(arr):
length = len(arr)
for i in range(length):
for j in range(0, length - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
data = [64, 34, 25, 12, 22, 11, 90]
print(organize_with_bubble(data))
How it works: Bubble sort operates by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. Each pass through the list places the largest unsorted element in its correct position at the end of the unsorted portion. This process continues until the entire list is sorted.
- Selection Sort
def arrange_with_selection(arr):
for i in range(len(arr)):
minimum_index = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[minimum_index]:
minimum_index = j
arr[i], arr[minimum_index] = arr[minimum_index], arr[i]
return arr
data = [64, 25, 12, 22, 11]
print(arrange_with_selection(data))
How it works: Selection sort works by dividing the list into a sorted and an unsorted region. It repeatedly selects the smallest element from the unsorted region and swaps it with the first element of that region. The sorted region grows from left to right with each iteration until the entire array is sorted.
- Insertion Sort
def sort_with_insertion(arr):
for i in range(1, len(arr)):
current_value = arr[i]
position = i - 1
while position >= 0 and current_value < arr[position]:
arr[position + 1] = arr[position]
position -= 1
arr[position + 1] = current_value
return arr
data = [12, 11, 13, 5, 6]
print(sort_with_insertion(data))
How it works: Insertion sort builds the final sorted array one item at a time. It takes each element and inserts it into its correct position within the already-sorted portion of the array. This is similar to how people naturally sort playing cards in their hands.
- Merge Sort
def arrange_with_merge(items):
if len(items) <= 1:
return items
midpoint = len(items) // 2
left_segment = items[:midpoint]
right_segment = items[midpoint:]
arrange_with_merge(left_segment)
arrange_with_merge(right_segment)
left_ptr = right_ptr = output_ptr = 0
while left_ptr < len(left_segment) and right_ptr < len(right_segment):
if left_segment[left_ptr] < right_segment[right_ptr]:
items[output_ptr] = left_segment[left_ptr]
left_ptr += 1
else:
items[output_ptr] = right_segment[right_ptr]
right_ptr += 1
output_ptr += 1
while left_ptr < len(left_segment):
items[output_ptr] = left_segment[left_ptr]
left_ptr += 1
output_ptr += 1
while right_ptr < len(right_segment):
items[output_ptr] = right_segment[right_ptr]
right_ptr += 1
output_ptr += 1
return items
data = [12, 11, 13, 5, 6, 7]
print(arrange_with_merge(data))
How it works: Merge sort employs the divide-and-conquer strategy. It recursively splits the array into smaller subarrays until each subarray contains a single element. Then, it merges these subarrays back together in sorted order, repeatedly combining smaller sorted lists into larger ones until the complete sorted array is reconstructed.
- Quick Sort
def organize_with_quick(arr):
if len(arr) <= 1:
return arr
pivot_element = arr[len(arr) // 2]
smaller = [x for x in arr if x < pivot_element]
equal = [x for x in arr if x == pivot_element]
larger = [x for x in arr if x > pivot_element]
return organize_with_quick(smaller) + equal + organize_with_quick(larger)
data = [3, 6, 8, 10, 1, 2, 1]
print(organize_with_quick(data))
How it works: Quick sort selects a pivot element and partitions the array into three groups: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. The algorithm recursively applies this process to the smaller and larger partitions. The pivot is correctly positioned in the final array, and this positioning is used to efficiently sort the remaining elements.
- Binary Search
def locate_with_binary(sorted_data, target):
left_index = 0
right_index = len(sorted_data) - 1
while left_index <= right_index:
middle = left_index + (right_index - left_index) // 2
if sorted_data[middle] == target:
return middle
elif sorted_data[middle] < target:
left_index = middle + 1
else:
right_index = middle - 1
return -1
data = [2, 3, 4, 10, 40]
target = 10
print(locate_with_binary(data, target))
How it works: Binary search efficiently locates a target value within a sorted array by repeatedly dividing the search interval in half. At each step, the algorithm compares the target value with the middle element of the interval. If they match, the search succeeds. If the target is less than the middle element, the search continues in the left half; otherwise, it continues in the right half. This approach eliminates half of the remaining elements with each comparison.
- Fibonacci Sequence
def generate_fibonacci(count):
if count <= 0:
return []
if count == 1:
return [0]
if count == 2:
return [0, 1]
fib_series = [0, 1]
for index in range(2, count):
fib_series.append(fib_series[index - 1] + fib_series[index - 2])
return fib_series
length = 10
print(generate_fibonacci(length))
How it works: The Fibonacci sequence is a series where each number equals the sum of the two preceding numbers, beginning with 0 and 1. This implementation builds the sequence iteratively, starting with the base cases and generating subsequent values by summing the two most recent elements in the sequence.
- Euclidean Algorithm for GCD
def compute_gcd(first, second):
while second != 0:
first, second = second, first % second
return first
value_a = 60
value_b = 48
print(compute_gcd(value_a, value_b))
How it works: The Euclidean algorithm efficiently computes the greatest common divisor of two integers by leveraging the mathematical principle that the GCD of two numbers also divides their difference. The algorithm repeatedly replaces the larger number with the remainder of dividing the larger by the smaller, continuing until one number becomes zero. The remaining non-zero number is the GCD.
- Depth-First Search
def traverse_dfs(graph_structure, starting_node, visited_nodes=None):
if visited_nodes is None:
visited_nodes = set()
visited_nodes.add(starting_node)
print(starting_node)
for adjacent in graph_structure[starting_node] - visited_nodes:
traverse_dfs(graph_structure, adjacent, visited_nodes)
return visited_nodes
network = {
'A': {'B', 'C'},
'B': {'A', 'D', 'E'},
'C': {'A', 'F'},
'D': {'B'},
'E': {'B', 'F'},
'F': {'C', 'E'}
}
traverse_dfs(network, 'A')
How it works: Depth-first search explores graph structures by going as deep as possible along each branch before backtracking. Starting from the initial node, the algorithm visits a node and then recursively explores each unvisited neighbor. When no unvisited neighbors exist, it backtracks to the previous node and continues exploring alternative paths. This approach systematically visits every reachable node in the graph.
- Breadth-First Search
from collections import deque
def explore_bfs(graph_structure, starting_node):
visited_nodes = set()
node_queue = deque([starting_node])
visited_nodes.add(starting_node)
while node_queue:
current = node_queue.popleft()
print(current)
for neighbor in graph_structure[current]:
if neighbor not in visited_nodes:
visited_nodes.add(neighbor)
node_queue.append(neighbor)
return visited_nodes
network = {
'A': {'B', 'C'},
'B': {'A', 'D', 'E'},
'C': {'A', 'F'},
'D': {'B'},
'E': {'B', 'F'},
'F': {'C', 'E'}
}
explore_bfs(network, 'A')
How it works: Breadth-first search examines graph structures level by level, starting from the initial node. The algorithm maintains a queue of nodes to visit and processes each node by first marking it as visited and then adding all its unvisited neighbors to the queue. This systematic approach ensures that nodes are visited in order of their distance from the starting node, making BFS particularly useful for finding the shortest path in unweighted graphs.
