Common Algorithms

Selection Sort

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.

Selection sort divides the list into sorted and unsorted portions. It repeatedly finds the minimum element from the unsorted portion and moves it to the end of the sorted portion.

Algorithm

  1. Find the minimum element in the unsorted portion
  2. Swap it with the first unsorted element
  3. Move the boundary between sorted and unsorted one position right
  4. Repeat until the entire list is sorted
find_minimum Scan unsorted portion to locate the smallest element

Basic Implementation

numbers
basic.py
Replay: real traced execution (multi-file project)
# 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 = [64, 25, 12, 22, 11]

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 = [29, 10, 14, 37, 13]

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 = [4, 3, 2, 1]

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

  1. numbers ← [64, 25, 12, 22, 11]

    20# Test selection sort21numbers→ [64, 25, 12, 22, 11] = [64, 25, 12, 22, 11]22#@numbers=[29, 10, 14, 37, 13], [4, 3, 2, 1]2324print("Before:", numbers[64, 25, 12, 22, 11])25selection_sort(numbers[64, 25, 12, 22, 11])26print("After: ", numbers)
    outputBefore: [64, 25, 12, 22, 11]

  2. n ← 5

    4def selection_sort(arr[64, 25, 12, 22, 11]):5    """Selection sort implementation"""6    n→ 5 = len(arr[64, 25, 12, 22, 11])

  3. min_index ← 0

    pass 1 of 4
    8# Selection sort implementation9for i0 in range(n5 - 1):10    # Find minimum in unsorted portion11    min_index→ 0 = i012    for j in range(i + 1, n):
    All 4 passes — pass 1 is the card above
    passimin_index
    100
    211
    322
    433

  4. for j in range(i + 1, n):

    pass 1 of 10
    11min_index = i12for j1 in range(i0 + 1, n5):13    if arr[j] < arr[min_index]:14        min_index = j
    All 10 passes — pass 1 is the card above
    passji
    110
    220
    330
    440
    521
    631
    741
    832
    942
    1043

  5. min_index ← 1

    pass 1 of 5
    12for j in range(i + 1, n):13    if arr[j]25 < arr[min_index]64:14        min_index→ 1 = j1
    All 5 passes — pass 1 is the card above
    passarr[j]arr[min_index]jmin_index
    1256411
    2122522
    3111244
    4122522
    5222533

  6. arr[i] ← 11, arr[min_index] ← 64

    16# Swap minimum with first unsorted element17arr[i]→ 11, arr[min_index]→ 64 = arr[min_index], arr[i]

  7. arr[i] ← 12, arr[min_index] ← 25

    16# Swap minimum with first unsorted element17arr[i]→ 12, arr[min_index]→ 25 = arr[min_index], arr[i]

  8. arr[i] ← 22, arr[min_index] ← 25

    16# Swap minimum with first unsorted element17arr[i]→ 22, arr[min_index]→ 25 = arr[min_index], arr[i]

  9. arr[i] ← 25, arr[min_index] ← 25

    16# Swap minimum with first unsorted element17arr[i]→ 25, arr[min_index]→ 25 = arr[min_index], arr[i]

  10. numbers ← [11, 12, 22, 25, 64]

    24print("Before:", numbers)25selection_sort(numbers→ [11, 12, 22, 25, 64])26print("After: ", numbers[11, 12, 22, 25, 64])
    outputAfter:  [11, 12, 22, 25, 64]

  1. numbers ← [29, 10, 14, 37, 13]

    20# Test selection sort21numbers→ [29, 10, 14, 37, 13] = [29, 10, 14, 37, 13]2223print("Before:", numbers[29, 10, 14, 37, 13])24selection_sort(numbers[29, 10, 14, 37, 13])25print("After: ", numbers)
    outputBefore: [29, 10, 14, 37, 13]

  2. n ← 5

    4def selection_sort(arr[29, 10, 14, 37, 13]):5    """Selection sort implementation"""6    n→ 5 = len(arr[29, 10, 14, 37, 13])

  3. min_index ← 0

    pass 1 of 4
    8# Selection sort implementation9for i0 in range(n5 - 1):10    # Find minimum in unsorted portion11    min_index→ 0 = i012    for j in range(i + 1, n):
    All 4 passes — pass 1 is the card above
    passimin_index
    100
    211
    322
    433

  4. for j in range(i + 1, n):

    pass 1 of 10
    11min_index = i12for j1 in range(i0 + 1, n5):13    if arr[j] < arr[min_index]:14        min_index = j
    All 10 passes — pass 1 is the card above
    passji
    110
    220
    330
    440
    521
    631
    741
    832
    942
    1043

  5. min_index ← 1

    pass 1 of 4
    12for j in range(i + 1, n):13    if arr[j]10 < arr[min_index]29:14        min_index→ 1 = j1
    All 4 passes — pass 1 is the card above
    passarr[j]arr[min_index]jmin_index
    1102911
    2142922
    3131444
    4293744

  6. arr[i] ← 10, arr[min_index] ← 29

    16# Swap minimum with first unsorted element17arr[i]→ 10, arr[min_index]→ 29 = arr[min_index], arr[i]

  7. arr[i] ← 13, arr[min_index] ← 29

    16# Swap minimum with first unsorted element17arr[i]→ 13, arr[min_index]→ 29 = arr[min_index], arr[i]

  8. arr[i] ← 14, arr[min_index] ← 14

    16# Swap minimum with first unsorted element17arr[i]→ 14, arr[min_index]→ 14 = arr[min_index], arr[i]

  9. arr[i] ← 29, arr[min_index] ← 37

    16# Swap minimum with first unsorted element17arr[i]→ 29, arr[min_index]→ 37 = arr[min_index], arr[i]

  10. numbers ← [10, 13, 14, 29, 37]

    23print("Before:", numbers)24selection_sort(numbers→ [10, 13, 14, 29, 37])25print("After: ", numbers[10, 13, 14, 29, 37])
    outputAfter:  [10, 13, 14, 29, 37]

  1. numbers ← [4, 3, 2, 1]

    20# Test selection sort21numbers→ [4, 3, 2, 1] = [4, 3, 2, 1]2223print("Before:", numbers[4, 3, 2, 1])24selection_sort(numbers[4, 3, 2, 1])25print("After: ", numbers)
    outputBefore: [4, 3, 2, 1]

  2. n ← 4

    4def selection_sort(arr[4, 3, 2, 1]):5    """Selection sort implementation"""6    n→ 4 = len(arr[4, 3, 2, 1])

  3. min_index ← 0

    pass 1 of 3
    8# Selection sort implementation9for i0 in range(n4 - 1):10    # Find minimum in unsorted portion11    min_index→ 0 = i012    for j in range(i + 1, n):
    All 3 passes — pass 1 is the card above
    passimin_index
    100
    211
    322

  4. for j in range(i + 1, n):

    pass 1 of 6
    11min_index = i12for j1 in range(i0 + 1, n4):13    if arr[j] < arr[min_index]:14        min_index = j
    All 6 passes — pass 1 is the card above
    passji
    110
    220
    330
    421
    531
    632

  5. min_index ← 1

    pass 1 of 4
    12for j in range(i + 1, n):13    if arr[j]3 < arr[min_index]4:14        min_index→ 1 = j1
    All 4 passes — pass 1 is the card above
    passarr[j]arr[min_index]jmin_index
    13411
    22322
    31233
    42322

  6. arr[i] ← 1, arr[min_index] ← 4

    16# Swap minimum with first unsorted element17arr[i]→ 1, arr[min_index]→ 4 = arr[min_index], arr[i]

  7. arr[i] ← 2, arr[min_index] ← 3

    16# Swap minimum with first unsorted element17arr[i]→ 2, arr[min_index]→ 3 = arr[min_index], arr[i]

  8. arr[i] ← 3, arr[min_index] ← 3

    16# Swap minimum with first unsorted element17arr[i]→ 3, arr[min_index]→ 3 = arr[min_index], arr[i]

  9. numbers ← [1, 2, 3, 4]

    23print("Before:", numbers)24selection_sort(numbers→ [1, 2, 3, 4])25print("After: ", numbers[1, 2, 3, 4])
    outputAfter:  [1, 2, 3, 4]

Trace Example

trace.py
Replay: real traced execution (multi-file project)
# 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)

  1. numbers ← [5, 2, 8, 1, 9]

    30# Test with trace31numbers→ [5, 2, 8, 1, 9] = [5, 2, 8, 1, 9]3233print("Initial:", numbers[5, 2, 8, 1, 9])34print()35selection_sort_trace(numbers[5, 2, 8, 1, 9])
    outputInitial: [5, 2, 8, 1, 9]

  2. n ← 5

    4def selection_sort_trace(arr[5, 2, 8, 1, 9]):5    """Selection sort with step-by-step trace"""6    n→ 5 = len(arr[5, 2, 8, 1, 9])

  3. min_index ← 0

    pass 1 of 4
    8# Trace each pass9for i0 in range(n5 - 1):10    print(f"Pass {i0 + 1}:")1112    # Find minimum13    min_index→ 0 = i014    for j in range(i + 1, n):
    outputPass 1:
    All 4 passes — pass 1 is the card above
    passimin_index
    100
    211
    322
    433

  4. for j in range(i + 1, n):

    pass 1 of 10
    13min_index = i14for j1 in range(i0 + 1, n5):15    if arr[j] < arr[min_index]:16        min_index = j
    All 10 passes — pass 1 is the card above
    passji
    110
    220
    330
    440
    521
    631
    741
    832
    942
    1043

  5. min_index ← 1

    pass 1 of 3
    14for j in range(i + 1, n):15    if arr[j]2 < arr[min_index]5:16        min_index→ 1 = j1
    All 3 passes — pass 1 is the card above
    passarr[j]arr[min_index]jmin_index
    12511
    21233
    35833

  6. print(f" Min in unsorted portion: {arr[min_index]} at index {min_inde…

    18print(f"  Min in unsorted portion: {arr[min_index]1} at index {min_index3}")
    output  Min in unsorted portion: 1 at index 3

  7. arr[i] ← 1, arr[min_index] ← 5

    pass 1 of 2
    20# Swap21if min_index3 != i0:22    print(f"  Swap positions {i0} and {min_index3}")23    arr[i]→ 1, arr[min_index]→ 5 = arr[min_index], arr[i]24else:
    output  Swap positions 0 and 3

  8. print(f" Result: {arr}")

    27print(f"  Result: {arr[1, 2, 8, 5, 9]}")
    output  Result: [1, 2, 8, 5, 9]

  9. print(f" Min in unsorted portion: {arr[min_index]} at index {min_inde…

    18print(f"  Min in unsorted portion: {arr[min_index]2} at index {min_index1}")
    output  Min in unsorted portion: 2 at index 1

  10. else:

    pass 1 of 2
    22    print(f"  Swap positions {i} and {min_index}")23    arr[i], arr[min_index] = arr[min_index], arr[i]24else:25    print("  Already in position")
    output  Already in position

  11. print(f" Result: {arr}")

    27print(f"  Result: {arr[1, 2, 8, 5, 9]}")
    output  Result: [1, 2, 8, 5, 9]

  12. print(f" Min in unsorted portion: {arr[min_index]} at index {min_inde…

    18print(f"  Min in unsorted portion: {arr[min_index]5} at index {min_index3}")
    output  Min in unsorted portion: 5 at index 3

  13. arr[i] ← 5, arr[min_index] ← 8

    pass 2 of 2
    20# Swap21if min_index3 != i2:22    print(f"  Swap positions {i2} and {min_index3}")23    arr[i]→ 5, arr[min_index]→ 8 = arr[min_index], arr[i]24else:
    output  Swap positions 2 and 3

  14. print(f" Result: {arr}")

    27print(f"  Result: {arr[1, 2, 5, 8, 9]}")
    output  Result: [1, 2, 5, 8, 9]

  15. print(f" Min in unsorted portion: {arr[min_index]} at index {min_inde…

    18print(f"  Min in unsorted portion: {arr[min_index]8} at index {min_index3}")
    output  Min in unsorted portion: 8 at index 3

  16. else:

    pass 2 of 2
    22    print(f"  Swap positions {i} and {min_index}")23    arr[i], arr[min_index] = arr[min_index], arr[i]24else:25    print("  Already in position")
    output  Already in position

  17. print(f" Result: {arr}")

    27print(f"  Result: {arr[1, 2, 5, 8, 9]}")
    output  Result: [1, 2, 5, 8, 9]

  18. numbers ← [1, 2, 5, 8, 9]

    34print()35selection_sort_trace(numbers→ [1, 2, 5, 8, 9])

Finding Maximum (Descending Sort)

find_max.py
Replay: real traced execution (multi-file project)
# 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)

  1. numbers ← [64, 25, 12, 22, 11]

    20# Test maximum variant21numbers→ [64, 25, 12, 22, 11] = [64, 25, 12, 22, 11]2223print("Before:", numbers[64, 25, 12, 22, 11])24selection_sort_max(numbers[64, 25, 12, 22, 11])25print("After: ", numbers)
    outputBefore: [64, 25, 12, 22, 11]

  2. n ← 5

    4def selection_sort_max(arr[64, 25, 12, 22, 11]):5    """Selection sort finding maximum"""6    n→ 5 = len(arr[64, 25, 12, 22, 11])

  3. max_index ← 0

    pass 1 of 4
    8# Selection sort finding maximum9for i4 in range(n5 - 1, 0, -1):10    # Find maximum in unsorted portion11    max_index→ 0 = 012    for j in range(1, i + 1):
    All 4 passes — pass 1 is the card above
    passimax_index
    140
    230
    320
    410

  4. for j in range(1, i + 1):

    pass 1 of 10
    11max_index = 012for j1 in range(1, i4 + 1):13    if arr[j] > arr[max_index]:14        max_index = j
    All 10 passes — pass 1 is the card above
    passji
    114
    224
    334
    444
    513
    623
    733
    812
    922
    1011

  5. arr[i] ← 64, arr[max_index] ← 11

    16# Swap maximum with last unsorted element17arr[i]→ 64, arr[max_index]→ 11 = arr[max_index], arr[i]

  6. max_index ← 1

    pass 1 of 3
    12for j in range(1, i + 1):13    if arr[j]25 > arr[max_index]11:14        max_index→ 1 = j1
    All 3 passes — pass 1 is the card above
    passarr[j]max_index
    1251
    2221
    3121

  7. arr[i] ← 25, arr[max_index] ← 22

    16# Swap maximum with last unsorted element17arr[i]→ 25, arr[max_index]→ 22 = arr[max_index], arr[i]

  8. arr[i] ← 22, arr[max_index] ← 12

    16# Swap maximum with last unsorted element17arr[i]→ 22, arr[max_index]→ 12 = arr[max_index], arr[i]

  9. arr[i] ← 12, arr[max_index] ← 12

    16# Swap maximum with last unsorted element17arr[i]→ 12, arr[max_index]→ 12 = arr[max_index], arr[i]

  10. numbers ← [11, 12, 22, 25, 64]

    23print("Before:", numbers)24selection_sort_max(numbers→ [11, 12, 22, 25, 64])25print("After: ", numbers[11, 12, 22, 25, 64])
    outputAfter:  [11, 12, 22, 25, 64]

Counting Operations

count.py
Replay: real traced execution (multi-file project)
# 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")

  1. sorted_list ← [1, 2, 3, 4, 5], reversed_list ← [5, 4, 3, 2, 1]

    26# Test on different inputs27sorted_list→ [1, 2, 3, 4, 5] = [1, 2, 3, 4, 5]28reversed_list→ [5, 4, 3, 2, 1] = [5, 4, 3, 2, 1]29random_list→ [3, 1, 4, 2, 5] = [3, 1, 4, 2, 5]3031comp1, swap1 = selection_sort_counted(sorted_list[1, 2, 3, 4, 5].copy())32print(f"Already sorted: {comp1} comparisons, {swap1} swaps")

  2. n ← 5, comparisons ← 0, swaps ← 0

    pass 1 of 3
    4def selection_sort_counted(arr[1, 2, 3, 4, 5]):5    """Selection sort that counts operations"""6    n→ 5 = len(arr[1, 2, 3, 4, 5])7    comparisons→ 0 = 08    swaps→ 0 = 0
    All 3 passes — pass 1 is the card above
    passarrncomparisonsswaps
    1[1, 2, 3, 4, 5]500
    2[5, 4, 3, 2, 1]500
    3[3, 1, 4, 2, 5]500

  3. min_index ← 0

    pass 1 of 12
    10# Count operations11for i0 in range(n5 - 1):12    min_index→ 0 = i0
    All 12 passes — pass 1 is the card above
    passimin_index
    100
    211
    322
    433
    500
    611
    722
    833
    900
    1011
    1122
    1233

  4. comparisons ← 1

    pass 1 of 30
    14for j1 in range(i0 + 1, n5):15    comparisons→ 1 += 116    if arr[j] < arr[min_index]:
    30 passes — pass 1 is the card above
    passjicomparisons
    1100 → 1
    2201 → 2
    3302 → 3
    4403 → 4
    5214 → 5
    6315 → 6
    7416 → 7
    8327 → 8
    9428 → 9
    ⋯ 19 more passes ⋯
    29428 → 9
    30439 → 10

  5. return comparisons, swaps

    23return comparisons10, swaps0

  6. comp1 ← 10, swap1 ← 0

    31comp1→ 10, swap1→ 0 = selection_sort_counted(sorted_list[1, 2, 3, 4, 5].copy())32print(f"Already sorted: {comp110} comparisons, {swap10} swaps")3334comp2, swap2 = selection_sort_counted(reversed_list[5, 4, 3, 2, 1].copy())35print(f"Reverse sorted: {comp2} comparisons, {swap2} swaps")
    outputAlready sorted: 10 comparisons, 0 swaps

  7. min_index ← 1

    pass 1 of 9
    15comparisons += 116if arr[j]4 < arr[min_index]5:17    min_index→ 1 = j1
    All 9 passes — pass 1 is the card above
    passarr[j]arr[min_index]jmin_index
    14511
    23422
    32333
    41244
    53422
    62333
    71311
    82333
    93433

  8. swaps ← 1, arr[i] ← 1, arr[min_index] ← 5

    pass 1 of 5
    19if min_index4 != i0:20    swaps→ 1 += 121    arr[i]→ 1, arr[min_index]→ 5 = arr[min_index], arr[i]
    All 5 passes — pass 1 is the card above
    passmin_indexiswapsarr[i]arr[min_index]
    1400 → 15 → 11 → 5
    2311 → 24 → 22 → 4
    3100 → 13 → 11 → 3
    4311 → 23 → 22 → 3
    5322 → 34 → 33 → 4

  9. return comparisons, swaps

    23return comparisons10, swaps2

  10. comp2 ← 10, swap2 ← 2

    34comp2→ 10, swap2→ 2 = selection_sort_counted(reversed_list[5, 4, 3, 2, 1].copy())35print(f"Reverse sorted: {comp210} comparisons, {swap22} swaps")3637comp3, swap3 = selection_sort_counted(random_list[3, 1, 4, 2, 5].copy())38print(f"Random order:   {comp3} comparisons, {swap3} swaps")
    outputReverse sorted: 10 comparisons, 2 swaps

  11. return comparisons, swaps

    23return comparisons10, swaps3

  12. comp3 ← 10, swap3 ← 3

    37comp3→ 10, swap3→ 3 = selection_sort_counted(random_list[3, 1, 4, 2, 5].copy())38print(f"Random order:   {comp310} comparisons, {swap33} swaps")
    outputRandom order:   10 comparisons, 3 swaps

Comparison with Bubble Sort

compare.py
Replay: real traced execution (multi-file project)
# 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!")

  1. reversed_list ← [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

    36# Compare swap counts37reversed_list→ [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]3839bubble_swaps = bubble_sort_swaps(reversed_list[10, 9, 8, 7, 6, 5, 4, 3, 2, 1].copy())40print(f"Bubble sort swaps: {bubble_swaps}")

  2. n ← 10, swaps ← 0

    4def bubble_sort_swaps(arr[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]):5    """Bubble sort counting swaps"""6    n→ 10 = len(arr[10, 9, 8, 7, 6, 5, 4, 3, 2, 1])7    swaps→ 0 = 0

  3. for i in range(n - 1):

    pass 1 of 9
    9for i0 in range(n10 - 1):10    for j in range(n - i - 1):11        if arr[j] > arr[j + 1]:
    All 9 passes — pass 1 is the card above
    passi
    10
    21
    32
    43
    54
    65
    76
    87
    98

  4. for j in range(n - i - 1):

    pass 1 of 45
    9for i in range(n - 1):10    for j0 in range(n10 - i0 - 1):11        if arr[j] > arr[j + 1]:12            swaps += 1
    45 passes — pass 1 is the card above
    passji
    100
    210
    320
    430
    540
    650
    760
    870
    980
    ⋯ 34 more passes ⋯
    4417
    4508

  5. swaps ← 1, arr[j] ← 9, arr[j + 1] ← 10

    pass 1 of 45
    10for j in range(n - i - 1):11    if arr[j]10 > arr[j + 1]9:12        swaps→ 1 += 113        arr[j]→ 9, arr[j + 1]→ 10 = arr[j + 1], arr[j]
    45 passes — pass 1 is the card above
    passswapsarr[j]arr[j + 1]
    10 → 110 → 99 → 10
    21 → 210 → 88 → 10
    32 → 310 → 77 → 10
    43 → 410 → 66 → 10
    54 → 510 → 55 → 10
    65 → 610 → 44 → 10
    76 → 710 → 33 → 10
    87 → 810 → 22 → 10
    98 → 910 → 11 → 10
    ⋯ 34 more passes ⋯
    4443 → 443 → 11 → 3
    4544 → 452 → 11 → 2

  6. return swaps

    15return swaps45

  7. bubble_swaps ← 45

    39bubble_swaps→ 45 = bubble_sort_swaps(reversed_list[10, 9, 8, 7, 6, 5, 4, 3, 2, 1].copy())40print(f"Bubble sort swaps: {bubble_swaps45}")4142selection_swaps = selection_sort_swaps(reversed_list[10, 9, 8, 7, 6, 5, 4, 3, 2, 1].copy())43print(f"Selection sort swaps: {selection_swaps}")
    outputBubble sort swaps: 45

  8. n ← 10, swaps ← 0

    18def selection_sort_swaps(arr[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]):19    """Selection sort counting swaps"""20    n→ 10 = len(arr[10, 9, 8, 7, 6, 5, 4, 3, 2, 1])21    swaps→ 0 = 0

  9. min_index ← 0

    pass 1 of 9
    23for i0 in range(n10 - 1):24    min_index→ 0 = i025    for j in range(i + 1, n):
    All 9 passes — pass 1 is the card above
    passimin_index
    100
    211
    322
    433
    544
    655
    766
    877
    988

  10. for j in range(i + 1, n):

    pass 1 of 45
    24min_index = i25for j1 in range(i0 + 1, n10):26    if arr[j] < arr[min_index]:27        min_index = j
    45 passes — pass 1 is the card above
    passji
    110
    220
    330
    440
    550
    660
    770
    880
    990
    ⋯ 34 more passes ⋯
    4497
    4598

  11. min_index ← 1

    pass 1 of 25
    25for j in range(i + 1, n):26    if arr[j]9 < arr[min_index]10:27        min_index→ 1 = j1
    25 passes — pass 1 is the card above
    passarr[j]arr[min_index]jmin_index
    191011
    28922
    37833
    46744
    55655
    64566
    73477
    82388
    91299
    ⋯ 14 more passes ⋯
    244566
    255655

  12. swaps ← 1, arr[i] ← 1, arr[min_index] ← 10

    pass 1 of 5
    29if min_index9 != i0:30    swaps→ 1 += 131    arr[i]→ 1, arr[min_index]→ 10 = arr[min_index], arr[i]
    All 5 passes — pass 1 is the card above
    passmin_indexiswapsarr[i]arr[min_index]
    1900 → 110 → 11 → 10
    2811 → 29 → 22 → 9
    3722 → 38 → 33 → 8
    4633 → 47 → 44 → 7
    5544 → 56 → 55 → 6

  13. return swaps

    33return swaps5

  14. selection_swaps ← 5

    42selection_swaps→ 5 = selection_sort_swaps(reversed_list[10, 9, 8, 7, 6, 5, 4, 3, 2, 1].copy())43print(f"Selection sort swaps: {selection_swaps5}")4445print("\nSelection sort makes fewer swaps!")
    outputSelection sort swaps: 5

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

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

Exercise: practical.py

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