Selection Sort — Practice Tasks¶

def selection_sort(arr):
    # TODO
    pass

def selection_sort_desc(arr):
    # TODO: find max instead of min
    pass

def selection_sort_count(arr):
    swaps = 0
    # TODO
    return swaps

def selection_sort_by(arr, key=lambda x: x):
    # TODO
    pass

def bidirectional_selection_sort(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        # TODO: find min AND max in one pass; place at lo and hi
        lo += 1; hi -= 1

def stable_selection_sort(arr):
    # TODO: use shifts instead of swap to preserve order
    pass

def selection_sort_recursive(arr, start=0):
    if start >= len(arr) - 1: return
    # TODO

class Node:
    def __init__(self, val, nxt=None):
        self.val = val; self.next = nxt

def selection_sort_linked(head):
    # TODO: find min in remaining list, swap values
    return head

def top_k_selection(arr, k):
    # TODO: do k passes of selection sort, return first k
    return arr[:k]

def cycle_sort(arr):
    # TODO: implement cycle sort - achieves min possible writes
    pass

class WriteCountingArray:
    def __init__(self, data):
        self._data = list(data); self.writes = 0
    def __getitem__(self, i): return self._data[i]
    def __setitem__(self, i, v):
        self._data[i] = v; self.writes += 1
    def __len__(self): return len(self._data)

# Compare write counts: Selection vs Insertion vs Bubble

import heapq
def heap_sort(arr):
    # TODO: build min-heap, repeatedly extract min into output
    pass