2.11 Common Algorithms

How it works: Checks each item one by one.

When used: Small datasets or unsorted data.

Python example:

def linear_search(data, target):
    for item in data:
        if item == target:
            return True
    return False

numbers = [4, 7, 1, 9]
print(linear_search(numbers, 7))
        

How it works: Repeatedly divides the data in half.

When used: Large datasets that are already sorted.

Python example:

def binary_search(data, target):
    low = 0
    high = len(data) - 1

    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return True
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return False

sorted_numbers = [1, 4, 7, 9]
print(binary_search(sorted_numbers, 7))
        

How it works: Repeatedly swaps adjacent values.

When used: Small or educational examples.

Python example:

def bubble_sort(data):
    for i in range(len(data)):
        for j in range(0, len(data) - i - 1):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]

numbers = [5, 3, 8, 2]
bubble_sort(numbers)
print(numbers)
        

How it works: Builds a sorted section one item at a time.

When used: Small or nearly sorted datasets.

Python example:

def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and data[j] > key:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key

numbers = [5, 3, 8, 2]
insertion_sort(numbers)
print(numbers)
        

How it works: Divides data and merges sorted halves.

When used: Large datasets requiring efficiency.

Python example:

def merge_sort(data):
    if len(data) > 1:
        mid = len(data) // 2
        left = data[:mid]
        right = data[mid:]

        merge_sort(left)
        merge_sort(right)

        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                data[k] = left[i]
                i += 1
            else:
                data[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            data[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            data[k] = right[j]
            j += 1
            k += 1

numbers = [5, 3, 8, 2]
merge_sort(numbers)
print(numbers)
        

• Linear search: Simple but slow on large lists
• Binary search: Fast but requires sorted data
• Bubble sort: Easy to understand, inefficient
• Insertion sort: Efficient for small datasets
• Merge sort: Fast and reliable, uses more memory

Algorithms can be compared by:

• Execution time
• Memory usage
• Number of comparisons

• Best case: Ideal scenario
• Worst case: Least efficient scenario
• Average case: Typical performance

Logical reasoning is used rather than formal Big‑O notation.

When choosing an algorithm, consider:

• Size of the dataset
• Whether the data is sorted
• Speed requirements
• Memory availability

Example: Binary search is more suitable than linear search when working with large, sorted datasets.