Selection sort algorithm in Python I'm learning basic algorithms and implementing them in Python. Critiques needed/welcome.

import pudb; pu.db
import random
def selection_sort(list_):
    """Implement selection_sort algorithm: iterate L to R in list, grab value
    if greatest and inserting into correct pos. After each loop, decrement
    length of iterated list by 1"""
    val_list, greatest = list(range(len(list_))), 0
    for num in range(len(list_)):
        greatest = val_list[-1]
        for val in val_list:
            if list_[greatest] &lt; list_[val]:
                greatest = val
        if list_[greatest] &gt; list_[val_list[-1]]:
            list_.insert(val, list_.pop(greatest))
            val_list.remove(val)
    return list_

if __name__ == '__main__':
    unsorted = list(range(9))
    random.shuffle(unsorted)
    assert selection_sort(unsorted) == list(range(9))
Most of my comments on your previous question apply here too, so I'll just summarize them quickly:


Debugging code that you forgot to remove.
Docstring written from the implementer's point of view.
Variable name respelled to avoid shadowing a built-in.
Test case not organized into a unit test.
Test case not very stringent (just 9 items).


In addition:


Given an array of length n, your algorithm makes n passes over the array, and in pass i it finds the ith largest item in the array (which at that point in the algorithm is the largest item in the first n − i positions) and swaps it into the position n − i − 1. This ought to be simple, but it's implemented in a very complex way, via the list val_list of indexes.

Here's a much simpler implementation:

def selection_sort(seq):
    """Sort the mutable sequence seq in place and return it."""
    for i in reversed(range(len(seq))):
        # Find the index of greatest item in seq[:i+1].
        greatest = 0
        for j in range(1, i + 1):
            if seq[j] &gt; seq[greatest]:
                greatest = j
        seq[i], seq[greatest] = seq[greatest], seq[i]
    return seq


Note that I've avoided testing seq[greatest] &gt; seq[i] before doing the swap, because I know that the only way this condition can fail is if greatest == i, and then the swap has no effect. So it's simplest to skip the test.

I could simplify this still further using Python's built-in function max:

def selection_sort(seq):
    """Sort the mutable sequence seq in place and return it."""
    for i in reversed(range(len(seq))):
        greatest = max(range(i + 1), key=seq.__getitem__)
        seq[i], seq[greatest] = seq[greatest], seq[i]
    return seq


But this seems like it's avoiding the spirit of the exercise: I mean, if I can use max, then why not sorted?