Ojasa Mirai
Python
Loading...
Advanced Loop Patterns and Algorithms
Loop patterns form the basis of algorithmic thinking. This section explores classic algorithms, their implementations, and performance characteristics.
Sorting Algorithms
Bubble Sort (O(n²))
def bubble_sort(items):
"""
Bubble sort: repeatedly swap adjacent elements if in wrong order.
Time complexity: O(n²) worst/average case, O(n) best case
Space complexity: O(1)
Stable: Yes
"""
n = len(items)
for i in range(n):
swapped = False
# Last i elements are already in place
for j in range(0, n - i - 1):
if items[j] > items[j + 1]:
items[j], items[j + 1] = items[j + 1], items[j]
swapped = True
# Optimization: stop if no swaps (already sorted)
if not swapped:
break
return items
# Usage
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_nums = bubble_sort(numbers.copy())
print(sorted_nums) # [11, 12, 22, 25, 34, 64, 90]
# Optimized version
def bubble_sort_optimized(items):
"""Bubble sort with early termination."""
n = len(items)
for i in range(n):
swapped = False
for j in range(n - i - 1):
if items[j] > items[j + 1]:
items[j], items[j + 1] = items[j + 1], items[j]
swapped = True
if not swapped:
return items
return itemsQuick Sort (O(n log n) average)
def quicksort(items):
"""
Quick sort: divide-and-conquer using pivot.
Time complexity: O(n log n) average, O(n²) worst case
Space complexity: O(log n) recursion depth
Stable: No (typically)
"""
def partition(arr, low, high):
"""Partition array around pivot."""
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quicksort_helper(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quicksort_helper(arr, low, pi - 1)
quicksort_helper(arr, pi + 1, high)
items_copy = items.copy()
quicksort_helper(items_copy, 0, len(items_copy) - 1)
return items_copy
# Usage
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_nums = quicksort(numbers)
print(sorted_nums) # [11, 12, 22, 25, 34, 64, 90]
# 3-way partition for duplicates
def quicksort_3way(items):
"""Quick sort optimized for arrays with duplicates."""
def partition_3way(arr, low, high):
"""Partition into < pivot, == pivot, > pivot."""
pivot = arr[low]
lt = low
gt = high
i = low + 1
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1
else:
i += 1
return lt, gt
def quicksort_helper(arr, low, high):
if low < high:
lt, gt = partition_3way(arr, low, high)
quicksort_helper(arr, low, lt - 1)
quicksort_helper(arr, gt + 1, high)
items_copy = items.copy()
quicksort_helper(items_copy, 0, len(items_copy) - 1)
return items_copy
# Better for arrays with many duplicates
numbers = [5, 3, 5, 1, 3, 5, 2, 1]
sorted_nums = quicksort_3way(numbers)
print(sorted_nums) # [1, 1, 2, 3, 3, 5, 5, 5]Merge Sort (O(n log n) guaranteed)
def merge_sort(items):
"""
Merge sort: divide-and-conquer with guaranteed O(n log n).
Time complexity: O(n log n) all cases
Space complexity: O(n)
Stable: Yes
"""
def merge(left, right):
"""Merge two sorted arrays."""
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
def merge_sort_helper(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_helper(arr[:mid])
right = merge_sort_helper(arr[mid:])
return merge(left, right)
return merge_sort_helper(items)
# Usage
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_nums = merge_sort(numbers)
print(sorted_nums) # [11, 12, 22, 25, 34, 64, 90]
# In-place merge sort variant
def merge_sort_inplace(items, left=0, right=None):
"""Merge sort with less memory overhead."""
if right is None:
right = len(items) - 1
if left < right:
mid = (left + right) // 2
merge_sort_inplace(items, left, mid)
merge_sort_inplace(items, mid + 1, right)
_merge_inplace(items, left, mid, right)
return items
def _merge_inplace(items, left, mid, right):
"""In-place merge helper."""
left_arr = items[left:mid + 1]
right_arr = items[mid + 1:right + 1]
i = j = 0
k = left
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] <= right_arr[j]:
items[k] = left_arr[i]
i += 1
else:
items[k] = right_arr[j]
j += 1
k += 1
while i < len(left_arr):
items[k] = left_arr[i]
i += 1
k += 1
while j < len(right_arr):
items[k] = right_arr[j]
j += 1
k += 1Search Algorithms
Binary Search
def binary_search(sorted_items, target):
"""
Binary search on sorted array.
Time complexity: O(log n)
Space complexity: O(1)
Requires: sorted array
"""
left, right = 0, len(sorted_items) - 1
while left <= right:
mid = (left + right) // 2
mid_value = sorted_items[mid]
if mid_value == target:
return mid
elif mid_value < target:
left = mid + 1
else:
right = mid - 1
return -1 # Not found
# Usage
numbers = [11, 12, 22, 25, 34, 64, 90]
print(binary_search(numbers, 25)) # 3
print(binary_search(numbers, 100)) # -1
# Variants
def binary_search_leftmost(sorted_items, target):
"""Find leftmost (first) occurrence."""
left, right = 0, len(sorted_items)
while left < right:
mid = (left + right) // 2
if sorted_items[mid] < target:
left = mid + 1
else:
right = mid
return left if left < len(sorted_items) and sorted_items[left] == target else -1
def binary_search_rightmost(sorted_items, target):
"""Find rightmost (last) occurrence."""
left, right = 0, len(sorted_items)
while left < right:
mid = (left + right) // 2
if sorted_items[mid] <= target:
left = mid + 1
else:
right = mid
return left - 1 if left > 0 and sorted_items[left - 1] == target else -1
# Find range of target
numbers = [1, 2, 2, 2, 3, 4, 5, 5, 5, 6]
target = 5
left = binary_search_leftmost(numbers, target)
right = binary_search_rightmost(numbers, target)
print(f"Target {target} found at indices {left} to {right}")Linear Search Optimizations
def linear_search(items, target):
"""Basic linear search O(n)."""
for i, item in enumerate(items):
if item == target:
return i
return -1
def linear_search_with_sentinel(items, target):
"""
Linear search with sentinel optimization.
Reduces conditional checks by placing target at end.
"""
n = len(items)
items.append(target) # Sentinel
i = 0
while items[i] != target:
i += 1
items.pop() # Remove sentinel
return i if i < n else -1
def linear_search_exponential_backing(items, target):
"""Search with exponential backing off."""
if not items:
return -1
# Exponential search to find range
bound = 1
while bound < len(items) and items[bound] < target:
bound *= 2
# Binary search in range
left = bound // 2
right = min(bound, len(items) - 1)
while left <= right:
mid = (left + right) // 2
if items[mid] == target:
return mid
elif items[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Dynamic Programming Patterns
Fibonacci with Memoization
def fibonacci_recursive(n):
"""Naive recursion - exponential time O(2ⁿ)."""
if n <= 1:
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
# Extremely slow for n > 30
def fibonacci_memoized(n, memo=None):
"""
Fibonacci with memoization.
Time complexity: O(n)
Space complexity: O(n)
"""
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memoized(n - 1, memo) + fibonacci_memoized(n - 2, memo)
return memo[n]
# Much faster
print(fibonacci_memoized(100))
def fibonacci_iterative(n):
"""
Iterative Fibonacci - best approach.
Time complexity: O(n)
Space complexity: O(1)
"""
if n <= 1:
return n
prev, curr = 0, 1
for _ in range(2, n + 1):
prev, curr = curr, prev + curr
return curr
print(fibonacci_iterative(100))
def fibonacci_generator(max_n):
"""Lazy Fibonacci generator."""
a, b = 0, 1
yield a
while a < max_n:
a, b = b, a + b
yield a
# Infinite sequence without memory overhead
for fib in fibonacci_generator(1000):
if fib > 500:
break
print(fib, end=' ')Longest Common Subsequence (LCS)
def lcs_recursive(text1, text2, i=None, j=None):
"""
Longest Common Subsequence - recursive approach.
Time complexity: O(2^(m+n))
"""
if i is None:
i = len(text1) - 1
if j is None:
j = len(text2) - 1
if i < 0 or j < 0:
return 0
if text1[i] == text2[j]:
return 1 + lcs_recursive(text1, text2, i - 1, j - 1)
else:
return max(
lcs_recursive(text1, text2, i - 1, j),
lcs_recursive(text1, text2, i, j - 1)
)
def lcs_memoized(text1, text2):
"""
LCS with memoization.
Time complexity: O(m × n)
Space complexity: O(m × n)
"""
m, n = len(text1), len(text2)
memo = {}
def helper(i, j):
if i < 0 or j < 0:
return 0
if (i, j) in memo:
return memo[(i, j)]
if text1[i] == text2[j]:
result = 1 + helper(i - 1, j - 1)
else:
result = max(helper(i - 1, j), helper(i, j - 1))
memo[(i, j)] = result
return result
return helper(m - 1, n - 1)
def lcs_iterative(text1, text2):
"""
LCS using dynamic programming table.
Bottom-up approach.
"""
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
def lcs_with_reconstruction(text1, text2):
"""LCS with sequence reconstruction."""
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# Reconstruct the subsequence
lcs = []
i, j = m, n
while i > 0 and j > 0:
if text1[i - 1] == text2[j - 1]:
lcs.append(text1[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1
return ''.join(reversed(lcs)), dp[m][n]
# Usage
seq1 = "abcdef"
seq2 = "fbdamn"
lcs_seq, length = lcs_with_reconstruction(seq1, seq2)
print(f"LCS: {lcs_seq}, Length: {length}") # "bd", 2Coin Change Problem
def coin_change_recursive(coins, amount):
"""
Minimum coins needed to make amount - recursive.
Time complexity: O(amount^coins)
"""
def helper(remaining):
if remaining == 0:
return 0
if remaining < 0:
return float('inf')
min_coins = float('inf')
for coin in coins:
result = helper(remaining - coin)
if result != float('inf'):
min_coins = min(min_coins, 1 + result)
return min_coins
result = helper(amount)
return result if result != float('inf') else -1
def coin_change_dp(coins, amount):
"""
Coin change using dynamic programming.
Time complexity: O(amount × coins)
Space complexity: O(amount)
"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin_amount in range(1, amount + 1):
for coin in coins:
if coin <= coin_amount:
dp[coin_amount] = min(dp[coin_amount], dp[coin_amount - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
def coin_change_with_path(coins, amount):
"""Coin change with actual coins used."""
dp = [float('inf')] * (amount + 1)
dp[0] = 0
parent = [-1] * (amount + 1)
for coin_amount in range(1, amount + 1):
for coin in coins:
if coin <= coin_amount and dp[coin_amount - coin] + 1 < dp[coin_amount]:
dp[coin_amount] = dp[coin_amount - coin] + 1
parent[coin_amount] = coin
if dp[amount] == float('inf'):
return -1, []
# Reconstruct path
coins_used = []
current = amount
while current > 0:
coin = parent[current]
coins_used.append(coin)
current -= coin
return dp[amount], coins_used
# Usage
coins = [1, 2, 5]
amount = 5
min_coins, coins_used = coin_change_with_path(coins, amount)
print(f"Minimum coins: {min_coins}, Used: {coins_used}") # 1, [5]Performance Analysis
import time
import sys
def compare_algorithms():
"""Compare different sorting algorithms."""
import random
data = list(range(1000, 0, -1)) # Already reversed
random.shuffle(data)
algorithms = {
'Bubble Sort': bubble_sort,
'Quick Sort': quicksort,
'Merge Sort': merge_sort,
}
for name, algo in algorithms.items():
data_copy = data.copy()
start = time.time()
sorted_data = algo(data_copy)
elapsed = time.time() - start
print(f"{name}: {elapsed*1000:.3f}ms")
# compare_algorithms()Key Takeaways
| Algorithm | Time | Space | Stable | Best For |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(1) | Yes | Small arrays |
| Quick Sort | O(n log n) avg | O(log n) | No | General purpose |
| Merge Sort | O(n log n) | O(n) | Yes | Guaranteed speed |
| Binary Search | O(log n) | O(1) | N/A | Sorted data |
| Fibonacci DP | O(n) | O(n) | N/A | Dynamic programming |
| LCS | O(m×n) | O(m×n) | N/A | String matching |
What's Next?
Explore these advanced topics:
- **Nested Loops (Advanced)**: Big O analysis and matrix operations
- **Debugging Loops (Advanced)**: Profiling and bottleneck detection
- **Best Practices (Advanced)**: Pythonic idioms and concurrent loops
- **While Loops (Advanced)**: Convergence algorithms
- **Loop Control (Advanced)**: Exception handling patterns
Master algorithmic thinking and solve complex problems efficiently!
Resources
Ojasa Mirai
Master AI-powered development skills through structured learning, real projects, and verified credentials. Whether you're upskilling your team or launching your career, we deliver the skills companies actually need.
Learn Deep • Build Real • Verify Skills • Launch Forward