A selection sort implemented in Python

Question

I'm not proficient at Python. My question is twofold: whether this selection sort algorithm implementation for number lists could be considered clean code (in the sense of being modular and maintainable), and how should I go about making it more Pythonic if necessary.

def selection_sort(the_list):
    for sorted_sublist_end_position in range(0, len(the_list) - 1):
        smallest_item_position = find_smallest_item_position(the_list, sorted_sublist_end_position)
        swap(the_list, sorted_sublist_end_position, smallest_item_position)
    return the_list

def find_smallest_item_position(the_list, position_before_unsorted_sublist):
    current_smallest_item_position = position_before_unsorted_sublist
    sublist_start_position = position_before_unsorted_sublist + 1
    for unsorted_sublist_position in range(sublist_start_position, len(the_list)):
        if the_list[unsorted_sublist_position] < the_list[current_smallest_item_position]:
            current_smallest_item_position = unsorted_sublist_position
    return current_smallest_item_position

def swap(a_list, i, j):
    aux = a_list[i]
    a_list[i] = a_list[j]
    a_list[j] = aux

print(selection_sort([2, 5, 4]))
print(selection_sort([5, 4, 2]))
print(selection_sort([]))

Potential issues I can think of:

• Variable names are very long (that would come from my Java background).

• I guess I could pass a single sublist to the second function, as the sublist start position is implicit, instead of two arguments. Would that make the code more Pythonic?

• Clean Code says functions should do one thing / be responsible by one thing. So I expect a function for instance to perform a single for. The second function performs both a for and a nested if, however if I extract a sub-function out of it the sub-function name will be just a rephrasing of what the sub-function does, which is not good. Should I go about doing that or is the function good enough as it is?

Answer 1

whether this selection sort... could be considered clean code (in the sense of being modular and maintainable)

Sorting (especially using a trivial algorithm like selection sort) is a simple thing to implement, so assuming you do it right, you will not need to maintain it in the future, like ever.

As for modularity I cannot give any definite answer since there isn't much to work with. There're only 3 functions, and it is unknown how or why you might be using them in the future. It is very well possible that you will not really need those helper functions at all.

Potential issues I can think of: Variable names are very long

That is true. Your code is very hard to read because the variable names are way too expressive. For example:

• The loop variables could be replaced with i without losing clarity since it's obvious that you're iterating over array indices
• current_smallest_item_position explains its purpose in too much detail and could be replaced current_min (it's understood that this is an index from the function itself)
• sublist_start_position doesn't explain its meaning well and could be replaced with search_from

Here's an example of how I'd rewrite your code changing the variable naming only:

def selection_sort(lst):
    for i in range(len(lst) - 1):
        j = find_smallest_item_position(lst, i)
        swap(lst, i, j)
    return lst

def find_smallest_item_position(lst, search_after):
    current_min = search_after
    search_from = search_after + 1
    for i in range(search_from, len(lst)):
        if lst[i] < lst[current_min]:
            current_min = i
    return current_min

(Notice how I replaced range(0, len(lst) - 1) with range(len(lst) - 1). That is because a starting index of 0 is implied when range receives a single argument.)

Looks much more clear now, doesn't it? The find_smallest_item_position function could be improved further by getting rid of current_min = search_after thing and inlining the search_from calculation:

def find_smallest_item_position(lst, current_min):
    for i in range(current_min + 1, len(lst)):
        if lst[i] < lst[current_min]:
            current_min = i
    return current_min

I guess I could pass a single sublist to the second function, as the sublist start position is implicit, instead of two arguments. Would that make the code more Pythonic?

Are you thinking of doing this instead?

def selection_sort(lst):
    for i in range(len(lst) - 1):
        j = find_smallest_item_position(lst, i)       # old version
        j = find_smallest_item_position(lst[i:]) + i  # new version
        swap(lst, i, j)
    return lst

That would be a terrible idea. Passing a searched-list and a starting-search-index is a normal thing to do. This version of the code, on the other hand, is not better in terms of readability but is worse in terms of performance since you have to make a (partial) copy of the list on every loop iteration.

Clean Code says functions should do one thing / be responsible by one thing

While that is true in general, I think you're too strict about this. If you start moving every single statement into a separate function, it'll only be detrimental for your code. IMO, you should only split big functions into smaller functions when you see that it becomes too complicated to reason about or when you realize that some logic could genuinely be reused in multiple places.

Your swap function is 100% a poor application of this principle. Notice how I did not include it my rewrite of your code - that is because nobody does that in Python. Instead, you can simply write:

lst[i], lst[j] = lst[j], lst[i]

No function needed at all.

Assuming find_smallest_item_position will not be reused elsewhere, I'd say there's no reason to make it a separate function too. And in case you think that your code would look ugly, with enough Python profficiency you could express it in a much more concise manner:

def find_smallest_item_position(lst, current_min):
    return min(range(current_min, len(lst)), key=lambda x: lst[x])

Which leads to a very clean selection_sort implementation:

def selection_sort(lst):
    for i in range(len(lst) - 1):
        j = min(range(i, len(lst)), key=lambda x: lst[x])
        lst[i], lst[j] = lst[j], lst[i]
    return lst

Answer 2

whether this selection sort algorithm implementation for number lists could be considered clean code (in the sense of being modular and maintainable)

The only style mistake you've made is that top-level items (function definitions, class definitions, etc.) in modules (source files) should be separated by two blank lines each, instead of one.

I think it's good to practise writing Python source files with the assumption that they will be modules in someone's project in the future. That sounds like your aim too. So mark "private members" (that you don't intend users to need to directly access) by prepending an underscore, and move your scripting stuff to the inside of a if __name__ == '__main__' block if you don't want it to run when a user uses import your_module:

def selection_sort(the_list):
    for sorted_sublist_end_position in range(0, len(the_list) - 1):
        smallest_item_position = _find_smallest_item_position(the_list, sorted_sublist_end_position)
        _swap(the_list, sorted_sublist_end_position, smallest_item_position)
    return the_list


def _find_smallest_item_position(the_list, position_before_unsorted_sublist):
    current_smallest_item_position = position_before_unsorted_sublist
    sublist_start_position = position_before_unsorted_sublist + 1
    for unsorted_sublist_position in range(sublist_start_position, len(the_list)):
        if the_list[unsorted_sublist_position] < the_list[current_smallest_item_position]:
            current_smallest_item_position = unsorted_sublist_position
    return current_smallest_item_position


def _swap(a_list, i, j):
    aux = a_list[i]
    a_list[i] = a_list[j]
    a_list[j] = aux


if __name__ == '__main__':
    print(selection_sort([2, 5, 4]))
    print(selection_sort([5, 4, 2]))
    print(selection_sort([]))

Add some docstrings and doctests too:

def selection_sort(the_list):
    r'''Sort the_list in-place using selection sort.

    :param the_list: a list of comparable items
    :return: the sorted list

    >>> a = [2, 5, 4]
    >>> selection_sort(a)
    [2, 4, 5]
    >>> a
    [2, 4, 5]
    >>> selection_sort([]) # don't crash!
    []
    '''
    for sorted_sublist_end_position in range(0, len(the_list) - 1):
        smallest_item_position = _find_smallest_item_position(the_list, sorted_sublist_end_position)
        _swap(the_list, sorted_sublist_end_position, smallest_item_position)
    return the_list

:param ...: ... and :return: ... belong to the Sphinx style docstring format, you could use any other of course.

The lines that look like REPL snippets are doctests. They provide example usage and testing facilities at the same time: run python -m doctest your_module.py to see if all the lines starting >>> produce the expected outputs.

It's also a good idea to use typehints wherever you can, especially in function signatures:

from typing import Protocol, TypeVar


class Comparable(Protocol):
    def __lt__(self, other):
        return NotImplemented


T = TypeVar('T', bound=Comparable)


def selection_sort(the_list: list[T]) -> list[T]:
    ...


def _find_smallest_item_position(the_list: list[T], position_before_unsorted_sublist: int) -> int:
    ...


def _swap(i: int, j: int) -> None:
    ...

Building a TypeVar and Protocol just to specify what types are sensible to pass into this self-evident usecase might be overkill, (the_list: list) -> list is a bare minimum that in this case I'd think is good enough.

how should I go about making it more Pythonic if necessary

• Use the idiomatic name lst for generic list instances, instead of the_list (which I think is a great and suitable name btw, there just exists a standard one which Pythoneers are used to)

• Don't specify the default 0 lower-bound in range: range(0, len(lst) - 1) and range(len(lst) - 1) are the same, but the second is the idiomatic one.

• Swap items using normal Python assignment syntax:

def _swap(lst: list[T], i: int, j: int) -> None:
    lst[i], lst[j] = lst[j], lst[i]

• Find every excuse you can to use slices, comprehensions, and Python's built-in functions instead of explicit procedural loops. In this use a slice and a min:

def _find_smallest_item_position(lst: list[T], position_before_unsorted_sublist: int) -> int:
    rest_of_list = lst[position_before_unsorted_sublist:]
    smallest_item = min(rest_of_list)
    return lst.index(smallest_item, position_before_unsorted_sublist)

Variable names are very long

I agree, your identifiers are too long which makes the code fatiguing on the eyes and mind. It's a pain to decipher code when you can't ingest an identifier at a glance.

Some of the meanings are wrong or not obvious too:

• position_before_unsorted_sublist is actually the index of the first item of the unsorted sublist, not the item before that one.
• sorted_sublist_end_position is actually the index of the first item that has not been sorted yet, not the index of the last item in the sorted-so-far sublist
• sublist_start_position is not the start position of the unsorted sublist (as its context would imply it is), instead it is the index of the second item of that sublist.
• unsorted_sublist_position is not an index relative to the unsorted sublist, instead it is an index relative to the original list. A better name is simply i, readers can see that it is constrained to the unsorted sublist because of the lower bound of the range range(sublist_start_position, ...)

Overthinking variable names can actually obfuscate them, just use familiar identifiers like i, start, stop etc. where appropriate. If you feel a need to use verbose variable names, it may also be a clue that your logic is unnecessarily complex too.

I would use these names instead:

def selection_sort(lst: list[T]) -> list[T]:
    r'''Sort lst in-place using selection sort.

    :param lst: a list of comparable items
    :return: the sorted list

    >>> a = [2, 5, 4]
    >>> selection_sort(a)
    [2, 4, 5]
    >>> a
    [2, 4, 5]
    >>> selection_sort([])
    []
    '''
    for i in range(len(lst) - 1):
        next_smallest = _locate_smallest_item(lst, i)
        _swap(lst, i, next_smallest)
    return lst


def _locate_smallest_item(lst: list[T], start: int) -> int:
    smallest_item = min(lst[start:])
    return lst.index(smallest_item, start)

I guess I could pass a single sublist to the second function, as the sublist start position is implicit, instead of two arguments. Would that make the code more Pythonic?

That would look something like this:

def selection_sort(the_list):
    for i in range(len(the_list) - 1):
        smallest_item_position = find_smallest_item_position(the_list[i:]) + i
        swap(the_list, i, smallest_item_position)
    return the_list

def find_smallest_item_position(sublist):
    current_smallest_item_position = 0
    for unsorted_sublist_position in enumerate(sublist):
        if sublist[unsorted_sublist_position] < sublist[current_smallest_item_position]:
            current_smallest_item_position = unsorted_sublist_position
    return current_smallest_item_position

It might be considered more Pythonic because you're using list slicing, avoiding typically low-level language implementation details like passing indexes, and you get a chance to use enumerate, but I don't think it's more readable in the end so I'd use your original version. I think the original function signature is more sensible because it's more similar to existing language APIs (like list.index, range, etc. - everything with start parameters), more in the spirit of selection sort, and avoids the awkward + i necessity - the meaning of which is not obvious at a glance IMO.

I don't think performance should ever be much of a consideration when writing Python. Readability, algorithmic clarity, adherence to Pythonic norms first and foremost. But generally loops are the slowest things you can do in Python, and builtins are the fastest. So a solution using slicing (which does copy the list - the snippet directly above is a fast O(n) slower than yours) and min is way faster than one written yourself with less Pythonic tools like procedural-style loops.

Clean Code says functions should do one thing / be responsible by one thing. So I expect a function for instance to perform a single for. The second function performs both a for and a nested if, however if I extract a sub-function out of it the sub-function name will be just a rephrasing of what the sub-function does, which is not good. Should I go about doing that or is the function good enough as it is?

You may have already read these: Should a method do one thing and be good at it? and its parent duplicate Should I extract specific functionality into a function and why?

You already know it yourself, it's bad to make functions for tasks that are too small. I think the use-a-for-loop-and-variable-to-find-the-most-X-in-a-list pattern that your find_smallest_item_position encapsulates is such an idiomatic and obvious conceptual unit that it would be a very bad idea to split it up further. You've already made correct choices about what deserves its own function.