Guided Project: Sorting I

Bubble Sort

Example Implementation

                        def bubble_sort(arr):
    n = len(arr)
    swapped = True
    while swapped:
        swapped = False
        for i in range(n - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
    return arr
                    

Time & Space Complexity:

Time Complexity: O(n²) - Nested loops result in quadratic time complexity
Space Complexity: O(1) - Only uses a constant amount of extra space

Example Usage:

numbers = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(numbers))  # [11, 12, 22, 25, 34, 64, 90]

Insertion Sort

Example Implementation

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

Time & Space Complexity:

Time Complexity: O(n²) in worst case, but can be O(n) if array is nearly sorted
Space Complexity: O(1) - In-place sorting algorithm

Example Usage:

numbers = [12, 11, 13, 5, 6]
print(insertion_sort(numbers))  # [5, 6, 11, 12, 13]

Algorithm Comparison

Algorithm	Best Case	Average Case	Worst Case	Space	Stable
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes

When to Use:

Bubble Sort: Simple implementation and good for educational purposes, but rarely used in practice due to inefficiency with large datasets.
Insertion Sort: Efficient for small datasets or nearly sorted arrays. Often used as part of more complex algorithms.

Practice Challenges

Challenge 1: Optimize Bubble Sort

Modify the bubble sort algorithm to skip comparisons for already sorted elements at the end of the array.

                        def optimized_bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr
                    

Challenge 2: Sort Objects by Property

Extend insertion sort to work with an array of objects, sorting by a specified property.

                        def insertion_sort_by_property(array, property_name):
    n = len(array)
    for i in range(1, n):
        current = array[i]
        j = i - 1
        while j >= 0 and array[j][property_name] > current[property_name]:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = current
    return array
                    

Example:

people = [
    { 'name': 'John', 'age': 30 },
    { 'name': 'Alice', 'age': 25 },
    { 'name': 'Bob', 'age': 35 }
]
print(insertion_sort_by_property(people, 'age'))
# Output: [{'name': 'Alice', 'age': 25}, {'name': 'John', 'age': 30}, {'name': 'Bob', 'age': 35}]

Additional Resources:

If you want more practice with sorting algorithms, check out these resources: