Implementation of the Selection Sort Algorithm

Question

I have tried to implement the Selection Sort Algorithm in two different ways, and I was just wondering if that is considered to be a valid implementation of that algorithm. Would that be also considered an efficient implementation of the algorithm, or are there different and more efficient ways?

Here are my implementations:

Implementation Attempt #1

def selection_sort(L: List[int]) -> List[int]:
    for i in range(len(L) - 1):
        j = i
        smallest_num = L[i]
        while j < len(L) - 1:
            if smallest_num > L[j + 1]:
                smallest_num = L[j + 1]
            j += 1
        L[L.index(smallest_num)], L[i] = L[i], L[L.index(smallest_num)]
    return L

Implementation Attempt #2

def selection_sort(L: List[int]):
    for i in range(len(L) - 1):
        j = i
        while j < len(L) - 1:
            swap_min(L, i)
            j += 1
    return L

def swap_min(L: List[int], n: int) -> None:
    smallet_num = min(L[n:])
    sm_indx = L.index(smallet_num)
    L[n], L[sm_indx] = L[sm_indx], L[n]

Answer 1

The use of L.index(smallest_num) makes neither of these implementations valid. Using the input list [1, 0, 1, 0, 1] as an example, both of your implementations give [1, 1, 0, 0, 1] as their result, and this is clearly not sorted correctly.

The reason your algorithm doesn't work on this input is that it contains duplicate elements, so the .index method doesn't always return the index you want it to; as the documentation says, the .index method returns the index of the first occurrence of the given value. That will not always be the index of the occurrence you want to find; sometimes, that index is in the "already-sorted" part of the list, so you end up swapping things back there where they don't belong.

A correct implementation of selection sort should search for the index of the minimum element in just the unsorted part of the list.

Answer 2

Your attempts lack docstrings.

Using common sequence operations is a nice touch - if only there was a
index_min = min_index(iterable, *[, key, default]) or a
min, index = min_index(iterable, *[, key, default]).

Why use for i in range(), but an open coded inner while-loop?

In Attempt #1, you keep just one piece of information about the smallest_num when a new one is found. If that was the index, you wouldn't have to re-discover it (let alone twice) - at the cost of an indexed access every time you need the value. Why, in the inner loop, add one to j in more than one place?

for j in range(i+1, len(L)):
    if L[j] < smallest_num:
        smallest_num = L[j]
        smallest_index = j

In Attempt #2, what do you expect the second time swap_min(L, i) gets executed? You don't use j in the inner loop. If it was index = L.index(smallest_num, n), index == n after the first call - no need for an explicit inner loop at all.