Selection Sort - Python Programming

When memory writes are expensive, such as writing to flash storage or slow external devices, minimizing the number of swap operations becomes important. Selection sort addresses this by guaranteeing exactly n-1 swaps regardless of input, making it useful when write operations are costly.

Comparison with Bubble Sort

basic.py

# Basic selection sort


def selection_sort(arr):
    """Selection sort implementation"""
    n = len(arr)

    # Selection sort implementation
    for i in range(n - 1):
        # Find minimum in unsorted portion
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # Swap minimum with first unsorted element
        arr[i], arr[min_index] = arr[min_index], arr[i]


# Test selection sort
numbers = 

print("Before:", numbers)
selection_sort(numbers)
print("After: ", numbers)

# Basic selection sort


def selection_sort(arr):
    """Selection sort implementation"""
    n = len(arr)

    # Selection sort implementation
    for i in range(n - 1):
        # Find minimum in unsorted portion
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # Swap minimum with first unsorted element
        arr[i], arr[min_index] = arr[min_index], arr[i]


# Test selection sort
numbers = 

print("Before:", numbers)
selection_sort(numbers)
print("After: ", numbers)

# Basic selection sort


def selection_sort(arr):
    """Selection sort implementation"""
    n = len(arr)

    # Selection sort implementation
    for i in range(n - 1):
        # Find minimum in unsorted portion
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # Swap minimum with first unsorted element
        arr[i], arr[min_index] = arr[min_index], arr[i]


# Test selection sort
numbers = 

print("Before:", numbers)
selection_sort(numbers)
print("After: ", numbers)

trace.py

# Selection sort with trace


def selection_sort_trace(arr):
    """Selection sort with step-by-step trace"""
    n = len(arr)

    # Trace each pass
    for i in range(n - 1):
        print(f"Pass {i + 1}:")

        # Find minimum
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        print(f"  Min in unsorted portion: {arr[min_index]} at index {min_index}")

        # Swap
        if min_index != i:
            print(f"  Swap positions {i} and {min_index}")
            arr[i], arr[min_index] = arr[min_index], arr[i]
        else:
            print("  Already in position")

        print(f"  Result: {arr}")


# Test with trace
numbers = [5, 2, 8, 1, 9]

print("Initial:", numbers)
print()
selection_sort_trace(numbers)

find_max.py

# Find maximum variant


def selection_sort_max(arr):
    """Selection sort finding maximum"""
    n = len(arr)

    # Selection sort finding maximum
    for i in range(n - 1, 0, -1):
        # Find maximum in unsorted portion
        max_index = 0
        for j in range(1, i + 1):
            if arr[j] > arr[max_index]:
                max_index = j

        # Swap maximum with last unsorted element
        arr[i], arr[max_index] = arr[max_index], arr[i]


# Test maximum variant
numbers = [64, 25, 12, 22, 11]

print("Before:", numbers)
selection_sort_max(numbers)
print("After: ", numbers)

count.py

# Count comparisons and swaps


def selection_sort_counted(arr):
    """Selection sort that counts operations"""
    n = len(arr)
    comparisons = 0
    swaps = 0

    # Count operations
    for i in range(n - 1):
        min_index = i

        for j in range(i + 1, n):
            comparisons += 1
            if arr[j] < arr[min_index]:
                min_index = j

        if min_index != i:
            swaps += 1
            arr[i], arr[min_index] = arr[min_index], arr[i]

    return comparisons, swaps


# Test on different inputs
sorted_list = [1, 2, 3, 4, 5]
reversed_list = [5, 4, 3, 2, 1]
random_list = [3, 1, 4, 2, 5]

comp1, swap1 = selection_sort_counted(sorted_list.copy())
print(f"Already sorted: {comp1} comparisons, {swap1} swaps")

comp2, swap2 = selection_sort_counted(reversed_list.copy())
print(f"Reverse sorted: {comp2} comparisons, {swap2} swaps")

comp3, swap3 = selection_sort_counted(random_list.copy())
print(f"Random order:   {comp3} comparisons, {swap3} swaps")

compare.py

# Compare with bubble sort


def bubble_sort_swaps(arr):
    """Bubble sort counting swaps"""
    n = len(arr)
    swaps = 0

    for i in range(n - 1):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                swaps += 1
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

    return swaps


def selection_sort_swaps(arr):
    """Selection sort counting swaps"""
    n = len(arr)
    swaps = 0

    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        if min_index != i:
            swaps += 1
            arr[i], arr[min_index] = arr[min_index], arr[i]

    return swaps


# Compare swap counts
reversed_list = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

bubble_swaps = bubble_sort_swaps(reversed_list.copy())
print(f"Bubble sort swaps: {bubble_swaps}")

selection_swaps = selection_sort_swaps(reversed_list.copy())
print(f"Selection sort swaps: {selection_swaps}")

print("\nSelection sort makes fewer swaps!")

Characteristics

Time complexity: O(n^2) - two nested loops
Space complexity: O(1) - sorts in place
Unstable: equal elements may change relative order
Best case: O(n^2) - always scans entire unsorted portion
Worst case: O(n^2) - same as best case
Fewer swaps: only n-1 swaps

find_minimum Scan unsorted portion to locate the smallest element

minimal_swaps Selection sort performs exactly n-1 swaps, regardless of input order

Exercise: practical.py

Implement selection sort to arrange a playlist by song duration, tracking and displaying the number of swaps performed