17
Day 17: Basic Algorithms
Chapter 17 • Advanced
55 min
Algorithms are step-by-step procedures for solving problems. They are the foundation of computer science and programming.
What are Algorithms?
An algorithm is a well-defined sequence of steps to solve a specific problem. It's like a recipe for solving computational problems.
Common Algorithm Types:
- Sorting Algorithms - Arrange data in order
- Searching Algorithms - Find specific data
- Recursive Algorithms - Functions that call themselves
- Iterative Algorithms - Use loops to solve problems
- Greedy Algorithms - Make locally optimal choices
- Dynamic Programming - Break problems into subproblems
Sorting Algorithms:
- Bubble Sort - Simple but inefficient
- Selection Sort - Find minimum and swap
- Insertion Sort - Insert elements in order
- Merge Sort - Divide and conquer approach
- Quick Sort - Efficient divide and conquer
Searching Algorithms:
- Linear Search - Check each element
- Binary Search - Efficient for sorted data
- Hash Search - Use hash tables for fast lookup
Algorithm Complexity:
- Time Complexity - How time grows with input size
- Space Complexity - How memory grows with input size
- Big O Notation - Describes algorithm efficiency
Hands-on Examples
Sorting Algorithms
# Bubble Sort
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
# Selection Sort
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# Binary Search
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Test sorting algorithms
numbers = [64, 34, 25, 12, 22, 11, 90]
print(f"Original array: {numbers}")
# Test bubble sort
bubble_result = bubble_sort(numbers.copy())
print(f"Bubble sort: {bubble_result}")
# Test selection sort
selection_result = selection_sort(numbers.copy())
print(f"Selection sort: {selection_result}")
# Test binary search
sorted_array = sorted(numbers)
print(f"Sorted array: {sorted_array}")
target = 25
index = binary_search(sorted_array, target)
print(f"Binary search for {target}: Index {index}")This example demonstrates basic sorting algorithms (bubble sort, selection sort) and binary search. These are fundamental algorithms every programmer should know.