C7 · Standard Algorithms

Spec reference: Section C - Programming Paradigms
Key idea: Understand and apply bubble sort, quick sort, insertion sort, linear search and binary search.

---

▶ Introudctionary to Sorting and Searching Algorithms

---

Insertion Sort

Insertion sort builds a sorted section one element at a time. It takes each element and inserts it into the correct position in the already-sorted portion.

Steps:

1. Start with the second element (index 1). Consider the first element already sorted.
2. Compare it with elements to its left, shifting them right until the correct position is found.
3. Insert the element there.
4. Repeat for each remaining element.

Trace: [5, 3, 8, 1]

Step	Sorted part	Current	Action
1	[5]	3	3 < 5, insert before 5 → [3,5]
2	[3,5]	8	8 > 5, insert after → [3,5,8]
3	[3,5,8]	1	1 < 8, < 5, < 3 → insert at front → [1,3,5,8]

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

Efficiency: O(n²) worst case, but O(n) on nearly sorted data - often faster in practice than bubble sort.

---

Quick Sort

Quick sort uses a divide-and-conquer approach. It picks a pivot element, partitions the list into values less than and greater than the pivot, then recursively sorts each partition.

Steps:

1. Choose a pivot (often the last element, or middle element).
2. Move all elements smaller than pivot to the left.
3. Move all elements larger than pivot to the right.
4. Recursively sort left and right partitions.

Example: [5, 3, 8, 1, 9, 2] - pivot = 5

Left of 5:  [3, 1, 2]
Pivot:       [5]
Right of 5: [8, 9]

Recursively sort [3,1,2] → [1,2,3]
Recursively sort [8,9] → [8,9]

Final: [1, 2, 3, 5, 8, 9] ✓

def quick_sort(lst):
    if len(lst) <= 1:
        return lst
    pivot = lst[len(lst) // 2]
    left  = [x for x in lst if x < pivot]
    mid   = [x for x in lst if x == pivot]
    right = [x for x in lst if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

Efficiency: O(n log n) average - much faster than bubble/insertion for large datasets.

---

Sorting algorithm comparison

Algorithm	Best case	Average	Worst case	Notes
Bubble sort	O(n)	O(n²)	O(n²)	Simple; good for small/nearly sorted
Insertion sort	O(n)	O(n²)	O(n²)	Efficient for nearly sorted data
Quick sort	O(n log n)	O(n log n)	O(n²)	Fast in practice; widely used

---

Searching algorithms

Linear Search (Serial Search)

Linear search checks every element in order from the first to the last until the target is found or the list is exhausted.

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i   # return index where found
    return -1          # -1 means not found

scores = [45, 82, 63, 71, 90]
print(linear_search(scores, 71))   # 3
print(linear_search(scores, 50))   # -1

Works on: unsorted or sorted lists.
Efficiency: O(n) - must check up to every element.

---

Binary Search

Binary search works on a sorted list. It repeatedly halves the search space:

1. Look at the middle element.
2. If it equals the target → found.
3. If target < middle → search the left half.
4. If target > middle → search the right half.
5. Repeat until found or the list is empty.

Trace: Find 71 in [45, 63, 71, 82, 90]

Step	Low	High	Mid index	Mid value	Action
1	0	4	2	71	Found! Return 2 ✓

Trace: Find 82 in [45, 63, 71, 82, 90]

Step	Low	High	Mid index	Mid value	Action
1	0	4	2	71	82 > 71 → search right
2	3	4	3	82	Found! Return 3 ✓

def binary_search(lst, target):
    low, high = 0, len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == target:
            return mid
        elif target < lst[mid]:
            high = mid - 1    # search left half
        else:
            low = mid + 1     # search right half
    return -1   # not found

Requirement: List must be sorted first.
Efficiency: O(log n) - each step halves the remaining search space.

---

Search comparison

	Linear Search	Binary Search
Requires sorted list?	No	Yes
Efficiency	O(n)	O(log n)
Best for	Small/unsorted lists	Large sorted lists
Maximum checks (100 items)	100	7
Maximum checks (1,000,000 items)	1,000,000	20

---

Test Yourself

Question 1 of 5

After one complete pass of bubble sort on [4, 2, 7, 1], what is the result?